1 条题解

  • 0
    @ 2026-5-7 10:01:37

    第一次写计算几何,爽了。

    我们肯定希望去枚举限制比较复杂的点,而限制比较简单的点用其他方式快速计算。

    于是考虑枚举 DD,注意到在枚举 AA 之后身体和尾巴可以分别计算,于是可以得到一个 O(n3)O(n^3) 的做法:

    枚举 D,AD,A,用桶维护到达两端距离相同的 B,CB,C 点对数量和 E,FE,F 点对数量。

    而如果 AA 确定了,E,FE,F 的有效范围是一个半平面。

    这启示我们可以用双指针维护 E,FE,F 的有效范围,用类似莫队的方式维护尾巴。

    具体的,枚举 DD 后对所有点极角排序,枚举 AA 的同时维护 E,FE,F 的范围。

    为了防止精度误差,可以用向量叉乘和点乘维护有效范围。

    即,DA×DE\vec{DA}\times \vec{DE} 控制它的上下,DADE\vec{DA}\cdot\vec{DE} 控制它的左右。

    之后,考虑身体如何维护。

    考虑连接这个四边形的对角线,会发现 BCBC 的中点一定落在 ADAD 上,并且这两条线垂直。

    那么就可以先预处理出 BCBC 的中点所在的那条与 BCBC 垂直的直线的位置,并把 BCBC 的中点挂上去。查询的时候 lower_bound 一下即可。

    需要注意的是这个题最好使用手写分数类,long double 好像不是很好过。

    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
    #define pb push_back
    int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;}
    const int MAXN=500010,N=5,inf=1e18,P=1e9;
    int n,ans;
    struct node{
        int x,y;
        node gt(int x,int y){
            int g=__gcd(x,y);
            x/=g,y/=g;
            if(y<0)x=-x,y=-y;
            return (node){x,y};
        }
        void bd(int _x,int _y){
            int g=__gcd(_x,_y);
            _x/=g,_y/=g;
            x=_x,y=_y;
            if(y<0)x=-x,y=-y;
        }
        bool operator<(const node&G)const{return x*G.y<y*G.x;}
        bool operator==(const node&G)const{return x*G.y==y*G.x;}
        bool operator<=(const node&G)const{return x*G.y<=y*G.x;}
        node operator+(const node&G){return gt(x*G.y+y*G.x,G.y*y);}
        node operator-(const node&G){return gt(x*G.y-y*G.x,G.y*y);}
        node operator*(const node&G){return gt(x*G.x,y*G.y);}
        node operator*(const int&G){return gt(x*G,y);}
        node operator/(const int&G){return gt(x,y*G);}
    };
    struct nd{
        int x,y;
        nd operator+(const nd&G)const{return (nd){x+G.x,y+G.y};}
        nd operator-(const nd&G)const{return (nd){x-G.x,y-G.y};}
        bool operator<(const nd&G)const{return atan2(x,y)<atan2(G.x,G.y);}
    }a[MAXN],p[MAXN],now;
    bool tp[MAXN];
    vector<int>G[MAXN];int m;
    struct line{
        node k,b;
        bool operator<(const line&G)const{return k==G.k?b<G.b:k<G.k;}
        bool operator==(const line&G)const{return k==G.k&&b==G.b;}
    };
    map<line,int>mp;
    map<int,int>mp1;
    int chk(nd y,nd x,nd z){return ((y.x-x.x)*(z.x-x.x)+(y.y-x.y)*(z.y-x.y));}
    int chk2(nd y,nd x,nd z){return ((y.x-x.x)*(z.y-x.y)-(y.y-x.y)*(z.x-x.x));}
    int dis(nd x,nd y){return (x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y);}
    void slv(){
        n=read();
        for(int i=1;i<=n;i++)a[i].x=read(),a[i].y=read();
        for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)if(a[i].y!=a[j].y){
            line tmp;
            tmp.k.bd(a[j].x-a[i].x,a[i].y-a[j].y);
            tmp.b=(node){a[i].y+a[j].y,2}-tmp.k*(node){a[i].x+a[j].x,2};
            if(!mp.count(tmp))mp[tmp]=++m;
            G[mp[tmp]].pb((a[i]+a[j]).x);
        }else{
            line tmp;
            tmp.k={1,0};
            tmp.b.bd(a[i].x+a[j].x,2);
            if(!mp.count(tmp))mp[tmp]=++m;
            G[mp[tmp]].pb(a[i].y);
        }
        for(int i=1;i<=m;i++)sort(G[i].begin(),G[i].end());
        for(int o=1;o<=n;o++){
            for(int j=1;j<n;j++)p[j]=j<o?a[j]-a[o]:a[j+1]-a[o];
            sort(p+1,p+n);
            for(int j=n;j<=n-1<<1;j++)p[j]=p[j-n+1],tp[j]=1;
            for(int j=1;j<=n-1<<1;j++)p[j]=p[j]+a[o];
            mp1.clear();
            int sum=0;
            for(int i=1,l=1,r=1;i<n;i++){
                while(r-i<n-1&&(chk(p[i],a[o],p[r])<0||chk2(p[i],a[o],p[r])<0||chk2(p[i],a[o],p[r])==0&&!tp[r])){
                    int tmp=dis(a[o],p[r]);
                    sum+=mp1[tmp];
                    mp1[tmp]++;
                    r++;
                }
                while(l-i<n-1&&l<r&&chk(p[i],a[o],p[l])>=0&&(chk2(p[i],a[o],p[l])<0||chk2(p[i],a[o],p[l])==0&&!tp[l])){
                    int tmp=dis(a[o],p[l]);
                    mp1[tmp]--;
                    sum-=mp1[tmp];
                    l++;
                }
                if(sum){
                    line tmp;int id=0;int L=0,R=0;
                    if(p[i].x!=a[o].x){
                        tmp.k.bd(p[i].y-a[o].y,p[i].x-a[o].x);
                        tmp.b=(node){p[i].y,1}-tmp.k*p[i].x;
                        if(mp.count(tmp))id=mp[tmp],L=min(p[i].x,a[o].x)*2,R=max(p[i].x,a[o].x)*2;
                    }
                    else {
                        tmp.k={1,0};
                        tmp.b={p[i].x,1};
                        if(mp.count(tmp))id=mp[tmp],L=min(p[i].y,a[o].y),R=max(p[i].y,a[o].y);
                    }
                    if(id){
                        int lt=upper_bound(G[id].begin(),G[id].end(),L)-G[id].begin(),rt=lower_bound(G[id].begin(),G[id].end(),R)-G[id].begin();
                        ans+=sum*(rt-lt);
                    }
                }
            }
        }
        printf("%lld",ans*4);
    }
    signed main(){
        freopen("1.in","r",stdin);freopen("1.out","w",stdout);
        slv();
        cerr<<clock()*1.0/CLOCKS_PER_SEC<<"s\n";
        return 0;
    }
    
    • 1

    信息

    ID
    2397
    时间
    2000ms
    内存
    512MiB
    难度
    10
    标签
    递交数
    2
    已通过
    1
    上传者