P1665 正方形计数 题解
题面
这是一道大水题
当然，可以用搜索什么的过，但是会慢一点
那么我们来理一理思路
我们枚举每一个可能正方形的对角线
首先我们有这样的一个正方形：
其中黑色的两个点是确定的，我们要得到另外两个红点的坐标……
使用毕达哥拉斯平方定理！使用锐角三角正切函数！求出斜率！暴力代入！ 这些方法会损精度的……
我们要用一种挺巧妙的方法：
连原来的两个点，求出中点：
然后从终点向x,y轴各引一条垂线与正方形的边相交
我们很容易就会证到
图中两个上色的三角形全等。
然后就很容易明白两条蓝线等长了啦QωQ
上面那条蓝线就是中点和另一个点的纵坐标差，
下面那条就是中点和待求点的横坐标差了，
酱紫就可以由中点坐标求到两个红点的纵坐标了嘛！
求横坐标也是如此啦……
然后呢，接下来有两种做法：
第一是用哈希表来找求出来的两个红点有没有出现过
第二是用一个布尔数组来存每个坐标是否有点
当然哈希会省点内存而且能处理带小数的情况
但是我很懒QωQ就用第二种了
还要注意一点！
在枚举时会把原来当过红点的点重新算一遍
所以最终答案要除以二
#include<cstdio>
#include<cstring>
using namespace std;
struct point
{
int x,y;//为什么不用double呢？因为由全等可以证明：当一个正方形两点都在整数坐标上时，
//其他两点也会在整点上
}a[510];
bool v[310][310];
int main()
{
int n;scanf("%d",&n);
int ans=0;
for(int i=1;i<=n;i++)
scanf("%d%d",&a[i].x,&a[i].y),
(a[i].x+=51)<<=1,(a[i].y+=51)<<=1,//防止负数，另外还要防止中点出现小数坐标
v[a[i].x][a[i].y]=1;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
int xmid=(a[i].x+a[j].x)>>1,ymid=(a[i].y+a[j].y)>>1;//中点的坐标
int x1=xmid-(a[i].y-ymid),y1=ymid-(xmid-a[i].x);//这是下面那个点
int x2=xmid+(a[i].y-ymid),y2=ymid+(xmid-a[i].x);//上面那个点明显就是反过来的啦
if(0<=x1&&x1<=300&&0<=y1&&y1<=300&&0<=x2&&x2<=300&&0<=y2&&y2<=300)
if(v[x1][y1]&&v[x2][y2])ans++;
}
printf("%d",ans>>1);
return 0;
}有问题欢迎私信哦QωQ