[JZOJ5953] 生死之境 [CodeForces 886F] Symmetric Projections【计算几何】

程序员文章站 2022-04-01 15:49:58

...

Description

在二维平面上给出n个格点，坐标范围在 $[-10^6,10^6]$
需要统计有多少条过原点的直线，满足所有点在这条直线上的投影成中心对称

$n\leq 1000$

Solution

考虑这个对称中心是什么。

有结论：对称中心一定为所有点的重心 $({\sum x\over n},{\sum y\over n})$ 在直线上的投影。

我们考虑一条过原点的直线，用其上的任意一个向量 $(p,q)$ 来表示，点积=模长*投影，那么全部乘以相同的模长仍然是对称的，因此就用点积来看。

考虑任意一对点 $(x_1,y_1),(x_2,y_2)$ ，它们的投影关于对称中心对称。
那对称中心的投影到原点距离等于 ${x_1p+y_1q+x_2p+y_2q\over 2}={x_1+x_2\over 2}p+{y_1+y_2\over 2}q$

多对点的情况是一样的，就是重心了

这样问题就简单许多。
枚举所有的点对，如果某个点对本身就关于重心对称，那么任意取直线它们都是对称的，删去。（一个点只能匹配一个，匹配过就不行了）

考虑剩下的点对，取这两点中点与重心的连线，过原点作连线的垂线，只有这条直线能让这个点对关于重心对称。

然而直接枚举判断还是会超时。
考虑合法的点对的条件，它一定覆盖了至少 $n\over 2$ 个点对

那么我们只需要判断出现了至少 $n\over 2$ 次的，已经匹配过的点不能再匹配，看能否覆盖整个点（还要判断自己与自己对称的情况）

这样的直线不会超过 $n$ 条，扫一遍点判断是 $O(n)$ 的，算上排序，总的复杂度就是 $O(n^2\log (n^2))$

Tips：使用atan2(y,x)函数可以直接获得一个向量与x轴正方向夹角，非常方便。

Code

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fod(i,a,b) for(int i=a;i>=b;--i)
#define N 1005
using namespace std;
const double pi=3.141592653589793;
int a[N][2],n,t,bf[N];
bool bz[N];
struct node
{
	int x,y;
	double c;
	friend bool operator <(node x,node y)
	{
		return x.c<y.c;
	}
}d[N*N];
int main()
{
	int t1;
	cin>>t1;
	while(t1--)
	{
		scanf("%d",&n);
		if(n<0) {printf("-1\n");continue;}
		double mx=0,my=0;
		fo(i,1,n) scanf("%d%d",&a[i][0],&a[i][1]),mx+=a[i][0],my+=a[i][1];
		mx=mx/1.0/n,my=my/1.0/n;
		int cnt=0;
		memset(bz,0,sizeof(bz));
		memset(bf,0,sizeof(bf));
		fo(i,1,n) if(a[i][0]==mx&&a[i][1]==my) bz[i]=1,cnt++;
		fo(i,1,n)
		{
			if(!bz[i])
			fo(j,i+1,n) 
			{
				if(!bz[j]&&(a[i][0]+a[j][0])/2.0==mx&&(a[i][1]+a[j][1])/2.0==my)
				{
					bz[i]=1,bz[j]=1,cnt+=2;
				} 
			}
		}
		if(cnt==n) {printf("-1\n");continue;}
		int num=0;
		fo(i,1,n)
		{
			if(!bz[i])
			fo(j,i+1,n)
			{
				if(!bz[j])
				{
					d[++num]=(node){i,j,atan2((double)(a[i][1]+a[j][1])/2.0-my,(double)(a[i][0]+a[j][0])/2.0-mx)};
					if(d[num].c<0) d[num].c+=pi;
					if(abs(d[num].c-pi)<1e-6) d[num].c=0;
				}
			}
		}
		sort(d+1,d+num+1);
		int c=1,st=1,ans=0;
		fo(i,1,num)
		{
			if(i!=num&&abs(d[i].c-d[i+1].c)<1e-6) c++;
			else
			{
				if(c>=(n-cnt)/2)
				{
					int ct=0;
					fo(j,st,i) 
					{
						if(bf[d[j].x]!=i&&bf[d[j].y]!=i) bf[d[j].x]=bf[d[j].y]=i;
					}
					fo(j,1,n) 
					{
						if(bf[j]==i||bz[j])ct++;
						else 
						{
							double p=atan2(a[j][1]-my,a[j][0]-mx);
							if(p<0) p+=pi;
							if(abs(p-pi)<1e-6) p=0;
							if(abs(p-d[st].c)<1e-6) ct++;
						}
					}
					if(ct==n) ans++;     
				}
				st=i+1;
				c=1;
			}
		}
		printf("%d\n",ans);
	}
}