#1172467 (C++23) No.2180 Comprehensive Line Segments

• 問題: No.2180 Comprehensive Line Segments
• ユーザー: butsurizuki
• 提出日時: 2026-07-22 12:07:46
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 1,474 ms / 5,000 ms
• コード長: 17,626 bytes
• コンパイル時間: 4,247 ms
• コンパイル使用メモリ: 367,544 KB
• 実行使用メモリ: 140,000 KB
• 最終ジャッジ日時: 2026-07-22 12:07:57
• 合計ジャッジ時間: 10,281 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
sample	AC * 4
other	AC * 25

ソースコード

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using i128 = __int128_t;

struct Vec {
    i64 x, y;

    bool operator==(const Vec& other) const {
        return x == other.x && y == other.y;
    }
    bool operator<(const Vec& other) const {
        return x != other.x ? x < other.x : y < other.y;
    }
};

i64 cross(const Vec& a, const Vec& b) {
    return a.x * b.y - a.y * b.x;
}

i64 dot(const Vec& a, const Vec& b) {
    return a.x * b.x + a.y * b.y;
}

Vec operator-(const Vec& a, const Vec& b) {
    return {a.x - b.x, a.y - b.y};
}

Vec normalize(Vec a) {
    const i64 g = gcd(abs(a.x), abs(a.y));
    a.x /= g;
    a.y /= g;
    return a;
}

int half_plane(const Vec& a) {
    return (a.y > 0 || (a.y == 0 && a.x >= 0)) ? 0 : 1;
}

struct Cone {
    // full == false:
    //   l == r なら方向 l の一本の半直線。
    //   l != r なら l から r まで反時計回りの角度区間。
    uint16_t l = 0, r = 0;
    bool include_l = true, include_r = true;
    bool full = false;
};

class ConeSystem {
public:
    vector<Vec> dir;
    int m = 0;
    int max_cones = 0;
    int full_id = -1;
    vector<int> exact_id;

private:
    vector<Cone> cones;
    unordered_map<uint32_t, int> cone_id;
    vector<int> trans;

    uint32_t cone_key(const Cone& c) const {
        return static_cast<uint32_t>(c.l)
             | (static_cast<uint32_t>(c.r) << 8)
             | (static_cast<uint32_t>(c.include_l) << 16)
             | (static_cast<uint32_t>(c.include_r) << 17)
             | (static_cast<uint32_t>(c.full) << 18);
    }

    int intern(const Cone& c) {
        const uint32_t key = cone_key(c);
        if (const auto it = cone_id.find(key); it != cone_id.end()) {
            return it->second;
        }
        const int id = static_cast<int>(cones.size());
        assert(id < max_cones);
        cones.push_back(c);
        cone_id.emplace(key, id);
        return id;
    }

    static int compare_fraction(i64 n1, i64 d1, i64 n2, i64 d2) {
        const i128 z = static_cast<i128>(n1) * d2
                     - static_cast<i128>(n2) * d1;
        return (z > 0) - (z < 0);
    }

    // 条件 A-Bt >= 0（non_strict=true）または A-Bt > 0 と
    // t>0 を同時に満たす t が存在するか。
    static bool feasible_t(
        const array<array<i64, 3>, 2>& cond,
        int count
    ) {
        i64 lower_num = 0, lower_den = 1;
        bool lower_inclusive = false;  // t > 0

        bool has_upper = false;
        i64 upper_num = 0, upper_den = 1;
        bool upper_inclusive = false;

        for (int i = 0; i < count; ++i) {
            const i64 A = cond[i][0];
            const i64 B = cond[i][1];
            const bool non_strict = static_cast<bool>(cond[i][2]);

            if (B == 0) {
                if (non_strict ? (A < 0) : (A <= 0)) return false;
                continue;
            }

            if (B > 0) {
                // t <= A/B または t < A/B
                const i64 num = A, den = B;
                if (!has_upper) {
                    has_upper = true;
                    upper_num = num;
                    upper_den = den;
                    upper_inclusive = non_strict;
                } else {
                    const int cmp = compare_fraction(
                        num, den, upper_num, upper_den
                    );
                    if (cmp < 0) {
                        upper_num = num;
                        upper_den = den;
                        upper_inclusive = non_strict;
                    } else if (cmp == 0) {
                        upper_inclusive =
                            upper_inclusive && non_strict;
                    }
                }
            } else {
                // t >= A/B または t > A/B
                const i64 num = -A, den = -B;
                const int cmp = compare_fraction(
                    num, den, lower_num, lower_den
                );
                if (cmp > 0) {
                    lower_num = num;
                    lower_den = den;
                    lower_inclusive = non_strict;
                } else if (cmp == 0) {
                    lower_inclusive =
                        lower_inclusive && non_strict;
                }
            }
        }

        if (!has_upper) return true;

        const int cmp = compare_fraction(
            lower_num, lower_den, upper_num, upper_den
        );
        if (cmp < 0) return true;
        if (cmp > 0) return false;
        return lower_inclusive && upper_inclusive;
    }

    // v = s*a + t*w, s>0,t>0 が解を持つか。
    static bool intersects_exact_ray(
        const Vec& a,
        const Vec& v,
        const Vec& w
    ) {
        const i64 den = cross(a, w);
        if (den != 0) {
            const i64 s_num = cross(v, w);
            const i64 t_num = cross(a, v);
            return den > 0
                ? (s_num > 0 && t_num > 0)
                : (s_num < 0 && t_num < 0);
        }

        if (cross(a, v) != 0) return false;

        if (dot(w, a) < 0) return true;
        return dot(v, a) > 0;
    }

    // 半直線 {v-t*w | t>0} が cone の正の部分と交わるか。
    bool ray_intersects_cone(
        int cid,
        const Vec& v,
        const Vec& w
    ) const {
        const Cone c = cones[cid];
        if (c.full) return true;

        if (c.l == c.r) {
            return intersects_exact_ray(dir[c.l], v, w);
        }

        const Vec L = dir[c.l];
        const Vec R = dir[c.r];
        const int width = (c.r - c.l + m) % m;

        if (width == m / 2) {
            array<array<i64, 3>, 2> cond{};
            cond[0] = {cross(L, v), cross(L, w), 0};

            if (feasible_t(cond, 1)) return true;
            if (c.include_l &&
                intersects_exact_ray(L, v, w)) {
                return true;
            }
            if (c.include_r &&
                intersects_exact_ray(R, v, w)) {
                return true;
            }
            return false;
        }

        array<array<i64, 3>, 2> cond{};
        cond[0] = {
            cross(L, v),
            cross(L, w),
            c.include_l
        };
        cond[1] = {
            cross(v, R),
            cross(w, R),
            c.include_r
        };
        return feasible_t(cond, 2);
    }

    // 各 dir[k] と、その直後の開区間の所属可否から
    // cone を復元する。
    int canonicalize(const unsigned char* belongs) {
        const int atom_count = 2 * m;

        bool all = true;
        for (int i = 0; i < atom_count; ++i) {
            if (!belongs[i]) {
                all = false;
                break;
            }
        }
        if (all) return full_id;

        int zero = 0;
        while (belongs[zero]) ++zero;

        int runs = 0, first = -1, last = -1;
        bool in_run = false;

        for (int step = 1; step < atom_count; ++step) {
            const int q = (zero + step) % atom_count;

            if (belongs[q] && !in_run) {
                in_run = true;
                ++runs;
                if (runs == 1) first = q;
            }

            if (!belongs[q] && in_run) {
                if (runs == 1) {
                    last = (q - 1 + atom_count) % atom_count;
                }
                in_run = false;
            }
        }

        if (in_run && runs == 1) {
            last = (zero - 1 + atom_count) % atom_count;
        }

        assert(runs == 1);

        int l, r;
        bool include_l, include_r;

        if ((first & 1) == 0) {
            l = first / 2;
            include_l = true;
        } else {
            l = first / 2;
            include_l = false;
        }

        if ((last & 1) == 0) {
            r = last / 2;
            include_r = true;
        } else {
            r = (last / 2 + 1) % m;
            include_r = false;
        }

        if (l == r) {
            assert(first == last && (first & 1) == 0);
            return exact_id[l];
        }

        const int width = (r - l + m) % m;
        assert(width <= m / 2);

        return intern(Cone{
            static_cast<uint16_t>(l),
            static_cast<uint16_t>(r),
            include_l,
            include_r,
            false
        });
    }

public:
    explicit ConeSystem(const vector<Vec>& p) {
        set<Vec> all_directions;
        const int n = static_cast<int>(p.size());

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i != j) {
                    all_directions.insert(
                        normalize(p[j] - p[i])
                    );
                }
            }
        }

        if (all_directions.empty()) {
            all_directions.insert({1, 0});
            all_directions.insert({-1, 0});
        }

        dir.assign(
            all_directions.begin(),
            all_directions.end()
        );

        sort(dir.begin(), dir.end(),
             [](const Vec& a, const Vec& b) {
            const int ha = half_plane(a);
            const int hb = half_plane(b);
            if (ha != hb) return ha < hb;
            return cross(a, b) > 0;
        });

        m = static_cast<int>(dir.size());
        assert(m % 2 == 0);

        max_cones = 1 + m + 2 * m * m;

        cones.reserve(max_cones);
        cone_id.reserve(2 * max_cones);
        trans.assign(max_cones * m, -1);

        full_id = intern(Cone{0, 0, true, true, true});

        exact_id.resize(m);
        for (int k = 0; k < m; ++k) {
            exact_id[k] = intern(Cone{
                static_cast<uint16_t>(k),
                static_cast<uint16_t>(k),
                true,
                true,
                false
            });
        }
    }

    bool contains_direction(int cid, int k) const {
        const Cone& c = cones[cid];

        if (c.full) return true;
        if (c.l == c.r) return k == c.l;

        const int total = (c.r - c.l + m) % m;
        const int dist = (k - c.l + m) % m;

        if (dist == 0) return c.include_l;
        if (dist == total) return c.include_r;

        return 0 < dist && dist < total;
    }

    int move_to_single_point(
        int cid,
        int target_direction
    ) {
        int& memo = trans[cid * m + target_direction];
        if (memo != -1) return memo;

        if (contains_direction(cid, target_direction)) {
            memo = full_id;
            return memo;
        }

        const Vec v = dir[target_direction];
        unsigned char belongs[264]{};

        for (int k = 0; k < m; ++k) {
            belongs[2 * k] =
                static_cast<unsigned char>(
                    k == target_direction ||
                    ray_intersects_cone(cid, v, dir[k])
                );

            Vec sample{
                dir[k].x + dir[(k + 1) % m].x,
                dir[k].y + dir[(k + 1) % m].y
            };

            if (sample.x == 0 && sample.y == 0) {
                sample = {-dir[k].y, dir[k].x};
            }

            belongs[2 * k + 1] =
                static_cast<unsigned char>(
                    ray_intersects_cone(cid, v, sample)
                );
        }

        memo = canonicalize(belongs);
        return memo;
    }
};

uint32_t pack_state(int mask, int point, int cone) {
    return static_cast<uint32_t>(mask)
         | (static_cast<uint32_t>(point) << 12)
         | (static_cast<uint32_t>(cone) << 16);
}

int solve(const vector<Vec>& p) {
    const int n = static_cast<int>(p.size());
    const int goal = (1 << n) - 1;

    ConeSystem cs(p);

    map<Vec, int> direction_index;
    for (int k = 0; k < cs.m; ++k) {
        direction_index[cs.dir[k]] = k;
    }

    vector<vector<int>> direction(
        n, vector<int>(n, -1)
    );

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i != j) {
                direction[i][j] =
                    direction_index[
                        normalize(p[j] - p[i])
                    ];
            }
        }
    }

    vector<vector<int>> on_segment(
        n, vector<int>(n)
    );

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i == j) {
                on_segment[i][j] = 1 << i;
                continue;
            }

            int mask = 0;
            const Vec v = p[j] - p[i];

            for (int k = 0; k < n; ++k) {
                const Vec w = p[k] - p[i];

                if (cross(v, w) == 0
                    && min(p[i].x, p[j].x) <= p[k].x
                    && p[k].x <= max(p[i].x, p[j].x)
                    && min(p[i].y, p[j].y) <= p[k].y
                    && p[k].y <= max(p[i].y, p[j].y)) {
                    mask |= 1 << k;
                }
            }

            on_segment[i][j] = mask;
        }
    }

    vector<int> block((1 << n) * n, -1);
    int block_count = 0;

    for (int mask = 1; mask <= goal; ++mask) {
        for (int i = 0; i < n; ++i) {
            if ((mask >> i) & 1) {
                block[mask * n + i] = block_count++;
            }
        }
    }

    const uint64_t bit_count =
        static_cast<uint64_t>(block_count)
        * cs.max_cones;

    vector<uint64_t> visited(
        (bit_count + 63) / 64, 0
    );

    auto mark =
        [&](int mask, int last, int cone) -> bool {
        const uint64_t q =
            static_cast<uint64_t>(
                block[mask * n + last]
            ) * cs.max_cones + cone;

        const uint64_t bit = 1ULL << (q & 63);
        uint64_t& word = visited[q >> 6];

        if (word & bit) return false;

        word |= bit;
        return true;
    };

    vector<uint32_t> current, next;
    current.reserve(1 << 12);

    auto add_state =
        [&](int mask,
            int last,
            int cone,
            vector<uint32_t>& q) {
        if (mark(mask, last, cone)) {
            q.push_back(pack_state(mask, last, cone));
        }
    };

    // 最初の線分で入力点を一つだけ登録する。
    for (int i = 0; i < n; ++i) {
        add_state(
            1 << i,
            i,
            cs.full_id,
            current
        );
    }

    // 最初の線分で入力点を二つ以上登録する。
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i == j) continue;

            add_state(
                on_segment[i][j],
                j,
                cs.exact_id[direction[i][j]],
                current
            );
        }
    }

    for (const uint32_t state : current) {
        if (static_cast<int>(state & 4095U) == goal) {
            return 1;
        }
    }

    for (int segment_count = 2;
         segment_count <= n;
         ++segment_count) {
        next.clear();

        if (next.capacity() < current.size() * 2) {
            next.reserve(current.size() * 2);
        }

        for (const uint32_t state : current) {
            const int mask =
                static_cast<int>(state & 4095U);

            const int last =
                static_cast<int>((state >> 12) & 15U);

            const int cone =
                static_cast<int>(state >> 16);

            const int remaining = goal ^ mask;

            // この線分では新しい点を登録しない接続遷移。
            if (cone != cs.full_id) {
                add_state(
                    mask,
                    last,
                    cs.full_id,
                    next
                );
            }

            // 新しい線分上で最初に登録する点 j。
            for (int bits = remaining;
                 bits;
                 bits &= bits - 1) {
                const int j =
                    __builtin_ctz(
                        static_cast<unsigned>(bits)
                    );

                const int next_cone =
                    cs.move_to_single_point(
                        cone,
                        direction[last][j]
                    );

                const int one_point_mask =
                    mask | (1 << j);

                if (one_point_mask == goal) {
                    return segment_count;
                }

                add_state(
                    one_point_mask,
                    j,
                    next_cone,
                    next
                );

                // 同じ線分上で最後に登録する別の点 k。
                const int without_j =
                    remaining ^ (1 << j);

                for (int more = without_j;
                     more;
                     more &= more - 1) {
                    const int k =
                        __builtin_ctz(
                            static_cast<unsigned>(more)
                        );

                    const int d = direction[j][k];

                    if (!cs.contains_direction(
                            next_cone, d)) {
                        continue;
                    }

                    const int new_mask =
                        mask | on_segment[j][k];

                    if (new_mask == goal) {
                        return segment_count;
                    }

                    add_state(
                        new_mask,
                        k,
                        cs.exact_id[d],
                        next
                    );
                }
            }
        }

        current.swap(next);
    }

    return n;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<Vec> p(n);
    for (Vec& v : p) {
        cin >> v.x >> v.y;
    }

    cout << solve(p) << '\n';
    return 0;
}