洛谷P5286/bzoj5489/loj3054 [HNOI2019]鱼 计算几何

题目分析

不难发现需要枚举D和A，然后鱼头鱼尾分别处理。

对于鱼尾，其实就是对着A的半平面内两条到D距离相等的线段组成的，枚举D后，将其他点极角排序，然后扫描线即可解决。

对于鱼头，也就是BC这条线段要垂直于AD，且BC的中点在AD上。则预处理枚举每个BC，将这个点对存入它的垂直平分线的vector中，按照中点排序。然后枚举AD，找到AD所在直线的vector，二分查找vector中中点在AD上的点对有多少个。

用了一堆map和vector，不开O2没法过。

代码

#include<bits/stdc++.h>
using namespace std;
#define RI register int
typedef long long LL;
typedef unsigned long long uLL;
typedef double db;
const int N=1005;
const db pi=acos(-1),eps=1e-10;
int n,lcnt;LL ans,tail_ans[N][N];
struct point{LL x,y;}p[N];

map<uLL,int> mp;
map<LL,int> mp_tail;
vector<int> ppair[1000005];
LL gcd(LL x,LL y) {return y?gcd(y,x%y):x;}
void head_prework() {
	for(RI i=1;i<=n;++i)
		for(RI j=i+1;j<=n;++j) {
			LL A=p[i].x-p[j].x,B=p[i].y-p[j].y,C,d=gcd(abs(A),abs(B));
			LL midx=(p[i].x+p[j].x)/2,midy=(p[i].y+p[j].y)/2;
			if(A<0||(A==0&&B<0)) A=-A,B=-B;
			A/=d,B/=d,C=-midx*A-midy*B;
			uLL has=A*100000007+B*10007+C;
			if(!mp[has]) mp[has]=++lcnt;
			ppair[mp[has]].push_back(p[i].y==p[j].y?midy:midx);
		}
	for(RI i=1;i<=lcnt;++i) sort(ppair[i].begin(),ppair[i].end());
}
void head_work() {
	for(RI i=1;i<=n;++i)
		for(RI j=i+1;j<=n;++j) {
			LL A=p[i].y-p[j].y,B=p[j].x-p[i].x,C,d=gcd(abs(A),abs(B));
			if(A<0||(A==0&&B<0)) A=-A,B=-B;
			A/=d,B/=d,C=-p[i].x*A-p[i].y*B;
			uLL has=A*100000007+B*10007+C;
			LL k1=(p[i].x==p[j].x?p[i].y:p[i].x);
			LL k2=(p[i].x==p[j].x?p[j].y:p[j].x);
			if(k1>k2) swap(k1,k2);
			LL nowans=0;
			if(mp.count(has)) {
				uLL t=mp[has];
				nowans=lower_bound(ppair[t].begin(),ppair[t].end(),k2)-
				upper_bound(ppair[t].begin(),ppair[t].end(),k1);
			}
			ans+=nowans*(tail_ans[i][j]+tail_ans[j][i]);
		}
}

struct Apoint{int id;db jd;}kp[N<<1];
bool cmp(Apoint A,Apoint B) {return A.jd<B.jd;}
LL getdis(int a,int b)
	{return (p[a].x-p[b].x)*(p[a].x-p[b].x)+(p[a].y-p[b].y)*(p[a].y-p[b].y);}
void tail_work() {
	for(RI i=1;i<=n;++i) {//D
		int m=0;
		for(RI j=1;j<=n;++j)
			if(j!=i) kp[++m]=(Apoint){j,atan2(p[j].y-p[i].y,p[j].x-p[i].x)};
		sort(kp+1,kp+1+m,cmp);
		for(RI j=1;j<=m;++j) kp[j+m]=kp[j],kp[j+m].jd+=pi+pi;
		LL nowans=0;mp_tail.clear();
		for(RI j=1,L=1,R=0;j<=m;++j) {//A
			while(kp[R+1].jd+eps<kp[j].jd+1.5*pi)
				++R,nowans+=mp_tail[getdis(i,kp[R].id)]++;
			while(kp[L].jd<kp[j].jd+0.5*pi+eps)
				nowans-=--mp_tail[getdis(i,kp[L].id)],++L;
			tail_ans[i][kp[j].id]=nowans;
		}
	}
}

int main()
{
	scanf("%d",&n);
	for(RI i=1;i<=n;++i)
		scanf("%lld%lld",&p[i].x,&p[i].y),p[i].x*=2,p[i].y*=2;
	head_prework(),tail_work(),head_work();
	printf("%lld\n",ans*4);
	return 0;
}