1 条题解
-
0
第一次写计算几何,爽了。
我们肯定希望去枚举限制比较复杂的点,而限制比较简单的点用其他方式快速计算。
于是考虑枚举 ,注意到在枚举 之后身体和尾巴可以分别计算,于是可以得到一个 的做法:
枚举 ,用桶维护到达两端距离相同的 点对数量和 点对数量。
而如果 确定了, 的有效范围是一个半平面。
这启示我们可以用双指针维护 的有效范围,用类似莫队的方式维护尾巴。
具体的,枚举 后对所有点极角排序,枚举 的同时维护 的范围。
为了防止精度误差,可以用向量叉乘和点乘维护有效范围。
即, 控制它的上下, 控制它的左右。
之后,考虑身体如何维护。
考虑连接这个四边形的对角线,会发现 的中点一定落在 上,并且这两条线垂直。
那么就可以先预处理出 的中点所在的那条与 垂直的直线的位置,并把 的中点挂上去。查询的时候
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
- 上传者