对称性Symmetry 题解
jzzcjb
·
·
题解
这大概是一道数学题？？反正觉得回到了初三。
首先 n^3 很容易想，无非 n^2 枚举两个点，O(n) 判断。
不如来做个脑筋急转弯。一个数集里有几种数？两种，等于1的和不等于1的。
由此，所有对称轴有几种？两种,经过点1的和不经过点1的。
所以我们可以固定一个点 1 ，枚举一个点 i 与 1 配对。假设这两个点之间有一条对称轴，这两个点是关于这条对称轴的一对对称点。就可以求出这条对称轴的方程。再 O(n) 判断，是不是对称轴。
这样就可以找出所有不经过点 1 的对称轴。因为假设有一条对称轴不经过点 1 ，既然它合法， 1 就一定有一个对称点。但是我们已经枚举了所有的点与 1 配对，所以这样的对称轴是不存在的，即得证。
那经过点 1 的对称轴又怎么办？可以再固定一个点 2 ，再求一遍。这次要求所有的对称轴合法的条件还要加上经过点 1 ，不然会算重。
这样就不重不漏的计算了所有不经过点 1 的、经过点 1 但不经过点 2 的，所有可能的对称轴。还漏了经过点 1 并且经过点 2 的怎么办？两点确定一条直线，单独判断一下就可以了。
某神犇结论：思路很明了，实现很虐心
首先要手推一发数学结论，就不在这里证了。
两点(x1,y1)(x2,y2)求过两点直线Ax+By+C=0
A=y2-y1 B=x1-x2 C=x2*y1-x1*y2
两点(x1,y1)(x2,y2)求两点间的对称轴Ax+By+C=0
A=x1-x2 B=y1-y2 C=-((x1+x2)(x1-x2)+(y1+y2)(y1-y2))/2
求(x',y')关于直线 Ax+By+C=0 的对称点(x0,y0)
设 k=-2*(A*x'+B*y'+C)/(A*A+B*B);
x0=x'+k*A;
y0=y'+k*B;
。
因为坐标有负数，所以要把所有坐标整体加上1w。
要记每个位置是否有点，要开一个2w*2w的布尔数组，不知道为什么没有爆空间(大概靠信仰)。
另外，精度要开到1e-10所有。
```
#include<iostream>
#include<cstdio>
#include<cmath>
#define eps 1e-10
using namespace std;
int n,cnt,x[100100],y[100100];
bool map[20001][20001];
bool dy(double x,double y){return ((x-y<=eps)||(y-x<=eps));}
bool is(double A,double B,double C){//判断某条直线是否是对称轴
for(int i=1;i<=n;i++){
/*
求(x',y')关于直线 Ax+By+C=0 的对称点(x0,y0)
设 k=-2*(A*x'+B*y'+C)/(A*A+B*B);
x0=x'+k*A;
y0=y'+k*B;
*/
double k=-2*(double)(A*x[i]+B*y[i]+C)/(A*A+B*B);
double xo=x[i]+k*A;int x0=round(xo);
double yo=y[i]+k*B;int y0=round(yo);
if(!dy(x0,xo)||!dy(y0,yo)) return 0;//不是整点
if(x0>20000||y0>20000) return 0;//越界
if(!map[x0][y0]) return 0;
}
return 1;
}
bool check(int a,int b){//以两点为一对对称点
//A=x1-x2 B=y1-y2 C=-((x1+x2)(x1-x2)+(y1+y2)(y1-y2))/2
double A=x[a]-x[b];
double B=y[a]-y[b];
double C=(double)-((x[a]*x[a]-x[b]*x[b])+(y[a]*y[a]-y[b]*y[b]))/2;
if(a!=1&&A*x[1]+B*y[1]+C!=0) return 0;
return is(A,B,C);
}
bool ok(int a,int b){//以两点所在直线为对称轴
//A=y2-y1 B=x1-x2 C=x2*y1-x1*y2
int A=y[b]-y[a];
int B=x[a]-x[b];
int C=x[b]*y[a]-x[a]*y[b];
return is(A,B,C);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)
cin>>x[i]>>y[i],x[i]+=10000,y[i]+=10000,
map[x[i]][y[i]]=1;
for(int i=2;i<=n;i++) cnt+=check(1,i);
for(int i=2;i<n;i++) cnt+=check(i,n);
cout<<cnt+ok(1,n);
}
```