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

• 問題: No.2180 Comprehensive Line Segments
• ユーザー: butsurizuki
• 提出日時: 2026-07-22 12:15:23
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 441 ms / 5,000 ms
• コード長: 13,129 bytes
• コンパイル時間: 3,935 ms
• コンパイル使用メモリ: 367,344 KB
• 実行使用メモリ: 8,960 KB
• 最終ジャッジ日時: 2026-07-22 12:15:30
• 合計ジャッジ時間: 6,896 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

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

ソースコード

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

struct Vec { long long x,y; };
Vec operator+(Vec a,Vec b){ return {a.x+b.x,a.y+b.y}; }
Vec operator-(Vec a,Vec b){ return {a.x-b.x,a.y-b.y}; }
i128 cross(Vec a,Vec b){ return (i128)a.x*b.y-(i128)a.y*b.x; }
i128 dot(Vec a,Vec b){ return (i128)a.x*b.x+(i128)a.y*b.y; }
Vec norm_dir(Vec v){
    long long g=gcd(llabs(v.x),llabs(v.y));
    return {v.x/g,v.y/g};
}
int half(Vec v){
    return (v.y>0 || (v.y==0 && v.x>0))?0:1;
}
bool angle_less(Vec a,Vec b){
    if(half(a)!=half(b)) return half(a)<half(b);
    return cross(a,b)>0;
}

struct Frac { long long n,d; }; // d>0
Frac make_frac(long long n,long long d){
    if(d<0) n=-n,d=-d;
    long long g=gcd(llabs(n),d);
    return {n/g,d/g};
}
bool operator<(Frac a,Frac b){
    return (i128)a.n*b.d<(i128)b.n*a.d;
}
bool operator==(Frac a,Frac b){
    return (i128)a.n*b.d==(i128)b.n*a.d;
}
Frac midpoint(Frac a,Frac b){
    return make_frac(
        (long long)((i128)a.n*b.d+(i128)b.n*a.d),
        (long long)((i128)2*a.d*b.d)
    );
}

struct Bits {
    array<uint64_t,5> w{};
};
void set_bit(Bits& b,int i){
    b.w[i>>6]|=1ULL<<(i&63);
}
bool get_bit(const Bits& b,int i){
    return (b.w[i>>6]>>(i&63))&1ULL;
}
void or_bits(Bits& a,const Bits& b){
    for(int i=0;i<5;i++) a.w[i]|=b.w[i];
}

struct Solver {
    int n,m,A,W;
    vector<Vec> p,dir;
    map<pair<long long,long long>,int> id;
    int dij[12][12]{};
    int between[12][12]{};

    // 有効な anchored state では変位 0 も常に可能。
    // Bits は非零方向のみを保持する。
    Bits ALL;
    vector<Bits> trans; // trans[w*A + source_atom]

    // 原子:
    // [0,m)   : ちょうど dir[i] の半直線
    // [m,2m)  : dir[i] から dir[i+1] までの開角領域
    // 原点はすべての原子錐に含める。
    bool in_atom(int a,i128 x,i128 y) const {
        if(x==0 && y==0) return true;

        auto cr=[&](Vec u){
            return (i128)u.x*y-(i128)u.y*x;
        };
        auto dt=[&](Vec u){
            return (i128)u.x*x+(i128)u.y*y;
        };

        if(a<m){
            return cr(dir[a])==0 && dt(dir[a])>0;
        }

        int i=a-m;
        int j=(i+1)%m;
        return cr(dir[i])>0
            && (i128)x*dir[j].y-(i128)y*dir[j].x>0;
    }

    Vec representative(int a) const {
        if(a<m) return dir[a];

        int i=a-m;
        int j=(i+1)%m;
        Vec q=dir[i]+dir[j];

        if(q.x!=0 || q.y!=0) return q;

        // 境界方向が互いに反対、すなわち開半平面。
        return {-dir[i].y,dir[i].x};
    }

    // source atom C に対し、
    // t>0 で w-t*d が C に入るものが存在するか。
    bool attainable(int source,Vec w,Vec d) const {
        Frac root[3];
        int nr=0;

        auto add_root=[&](long long a,long long b){
            if(b==0) return;
            if(b<0) a=-a,b=-b;
            if(a>0) root[nr++]={a,b};
        };

        auto add_line=[&](Vec u){
            add_root(
                (long long)cross(u,w),
                (long long)cross(u,d)
            );
        };

        if(source<m){
            add_line(dir[source]);
        }else{
            int i=source-m;
            add_line(dir[i]);
            add_line(dir[(i+1)%m]);
        }

        // w-t*d=0 となる臨界値。
        if(cross(w,d)==0 && dot(w,d)>0){
            if(d.x!=0) add_root(w.x,d.x);
            else       add_root(w.y,d.y);
        }

        for(int i=0;i<nr;i++){
            for(int j=i+1;j<nr;j++){
                if(root[j]<root[i]) swap(root[i],root[j]);
            }
        }

        int k=0;
        for(int i=0;i<nr;i++){
            if(k==0 || !(root[i]==root[k-1])){
                root[k++]=root[i];
            }
        }
        nr=k;

        auto good=[&](Frac t){
            i128 x=(i128)t.d*w.x-(i128)t.n*d.x;
            i128 y=(i128)t.d*w.y-(i128)t.n*d.y;
            return in_atom(source,x,y);
        };

        if(nr==0) return good({1,1});

        // 臨界値そのもの。
        for(int i=0;i<nr;i++){
            if(good(root[i])) return true;
        }

        // (0, root[0])
        if(good({root[0].n,2*root[0].d})) return true;

        // 隣接する臨界値の間。
        for(int i=0;i+1<nr;i++){
            if(good(midpoint(root[i],root[i+1]))) return true;
        }

        // (root.back(), +infinity)
        if(good({
            root[nr-1].n+root[nr-1].d,
            root[nr-1].d
        })) return true;

        return false;
    }

    Bits advance(const Bits& possible,int w) const {
        // 現在の端点を新しい点に一致させられる。
        if(get_bit(possible,w)) return ALL;

        Bits ans;

        // 現在の端点を以前の最後の入力点自身に置けるため、
        // 少なくとも w 方向へは進める。
        set_bit(ans,w);

        for(int q=0;q<W;q++){
            uint64_t x=possible.w[q];
            while(x){
                int b=__builtin_ctzll(x);
                int a=(q<<6)+b;

                if(a<A){
                    or_bits(ans,trans[w*A+a]);
                }

                x&=x-1;
            }
        }

        return ans;
    }

    int solve(){
        cin>>n;
        p.resize(n);
        for(Vec& q:p) cin>>q.x>>q.y;

        if(n==1) return 1;

        set<pair<long long,long long>> ds;

        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(i==j) continue;

                Vec d=norm_dir(p[j]-p[i]);
                ds.insert({d.x,d.y});
            }
        }

        for(auto [x,y]:ds){
            dir.push_back({x,y});
        }

        sort(dir.begin(),dir.end(),angle_less);

        m=(int)dir.size();
        A=2*m;
        W=(A+63)/64;

        for(int i=0;i<m;i++){
            id[{dir[i].x,dir[i].y}]=i;
        }

        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(i==j) continue;

                Vec v=p[j]-p[i];
                Vec nd=norm_dir(v);

                dij[i][j]=id[{nd.x,nd.y}];

                int mask=0;

                for(int k=0;k<n;k++){
                    Vec a=p[k]-p[i];
                    Vec b=p[k]-p[j];

                    if(cross(v,a)==0 && dot(a,b)<=0){
                        mask|=1<<k;
                    }
                }

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

        for(int a=0;a<A;a++){
            set_bit(ALL,a);
        }

        vector<Vec> rep(A);
        for(int a=0;a<A;a++){
            rep[a]=representative(a);
        }

        // 各 w、各入力原子から、到達可能な方向原子を前計算。
        trans.resize(m*A);

        for(int w=0;w<m;w++){
            for(int s=0;s<A;s++){
                Bits& z=trans[w*A+s];

                // dir[w] は D の要素なので、開角原子の内部にはない。
                // s==w のときだけ現在端点を新しい点に一致させられる。
                if(s==w){
                    z=ALL;
                }else{
                    for(int t=0;t<A;t++){
                        if(attainable(s,dir[w],rep[t])){
                            set_bit(z,t);
                        }
                    }
                }
            }
        }

        int full=(1<<n)-1;
        int S=(1<<n)*n;

        // cur[mask,last]:
        // 現在の線分本数で可能な非零端点方向原子の和集合。
        vector<Bits> cur(S),nxt(S);
        vector<uint8_t> ok(S),nok(S);
        vector<uint8_t> free_cur(1<<n),free_nxt(1<<n);

        vector<int> active,nactive;
        vector<int> factive,nfactive;

        active.reserve(S);
        nactive.reserve(S);

        auto add=[
            &
        ](
            vector<Bits>& d,
            vector<uint8_t>& used,
            vector<int>& list,
            int mask,
            int last,
            const Bits& val
        ){
            int z=mask*n+last;

            if(!used[z]){
                used[z]=1;
                list.push_back(z);
            }

            or_bits(d[z],val);
        };

        auto add_free=[
            &
        ](
            vector<uint8_t>& used,
            vector<int>& list,
            int mask
        ){
            if(!used[mask]){
                used[mask]=1;
                list.push_back(mask);
            }
        };

        // 最初の線分が新しく確定被覆する点が 0 個。
        add_free(free_cur,factive,0);

        // 最初の線分が新しく確定被覆する点が 1 個。
        for(int i=0;i<n;i++){
            add(cur,ok,active,1<<i,i,ALL);
        }

        // 最初の線分が新しく確定被覆する点が 2 個以上。
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(i==j) continue;

                Bits ray;
                set_bit(ray,dij[i][j]);

                add(
                    cur,
                    ok,
                    active,
                    between[i][j],
                    j,
                    ray
                );
            }
        }

        for(int z:active){
            if(z/n==full) return 1;
        }

        // N>=2 なら、P_0,P_1,...,P_{N-1} を順に結べば
        // N-1 本で必ず被覆できる。
        for(int cost=1;cost<n-1;cost++){
            for(int z:nactive){
                nxt[z]=Bits{};
                nok[z]=0;
            }
            nactive.clear();

            for(int mask:nfactive){
                free_nxt[mask]=0;
            }
            nfactive.clear();

            // anchored states
            for(int z:active){
                int mask=z/n;
                int last=z%n;
                int rem=full^mask;

                // 新しい点を 0 個通る線分。
                add_free(free_nxt,nfactive,mask);

                // 最初の新しい点 j を選ぶ。
                for(int jj=rem;jj;jj&=jj-1){
                    int j=__builtin_ctz(jj);

                    Bits after=advance(
                        cur[z],
                        dij[last][j]
                    );

                    // この線分が新しい点 j だけを確定被覆する場合。
                    int nm=mask|(1<<j);

                    if(nm==full) return cost+1;

                    add(
                        nxt,
                        nok,
                        nactive,
                        nm,
                        j,
                        after
                    );

                    // 同じ線分上の最後の新しい点 k を選ぶ。
                    int kr=rem&~(1<<j);

                    for(int kk=kr;kk;kk&=kk-1){
                        int k=__builtin_ctz(kk);
                        int d=dij[j][k];

                        if(!get_bit(after,d)) continue;

                        int mm=mask|between[j][k];

                        if(mm==full) return cost+1;

                        Bits ray;
                        set_bit(ray,d);

                        add(
                            nxt,
                            nok,
                            nactive,
                            mm,
                            k,
                            ray
                        );
                    }
                }
            }

            // free states
            for(int mask:factive){
                int rem=full^mask;

                // さらに新しい点を 0 個通る線分。
                add_free(free_nxt,nfactive,mask);

                for(int jj=rem;jj;jj&=jj-1){
                    int j=__builtin_ctz(jj);
                    int nm=mask|(1<<j);

                    // 任意位置から j だけを通るなら、
                    // 終点方向も任意にできる。
                    if(nm==full) return cost+1;

                    add(
                        nxt,
                        nok,
                        nactive,
                        nm,
                        j,
                        ALL
                    );

                    // 任意位置から j,k の順に通る。
                    int kr=rem&~(1<<j);

                    for(int kk=kr;kk;kk&=kk-1){
                        int k=__builtin_ctz(kk);
                        int d=dij[j][k];

                        int mm=mask|between[j][k];

                        if(mm==full) return cost+1;

                        Bits ray;
                        set_bit(ray,d);

                        add(
                            nxt,
                            nok,
                            nactive,
                            mm,
                            k,
                            ray
                        );
                    }
                }
            }

            cur.swap(nxt);
            ok.swap(nok);
            active.swap(nactive);

            free_cur.swap(free_nxt);
            factive.swap(nfactive);
        }

        return n-1;
    }
};

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

    Solver solver;
    cout<<solver.solve()<<'\n';
}