自动搬运

查看原文

来自洛谷，原作者为

	jzzcjb **

搬运于2025-08-24 21:44:44，当前版本为作者最后更新于2018-08-29 21:57:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这大概是一道数学题？？反正觉得回到了初三。

首先 $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;

$O(n)$ 判断的方法是枚举一个点，求出它的对称点，如果对称点的位置上有点，就继续；否则这条直线不合法；或者它的对称点根本没有落到整点上或超出了范围，也会不合法 。

因为坐标有负数，所以要把所有坐标整体加上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);
}