题意:
给出一些平面上点的坐标,用其中的点做顶点,求其中能组成正方形的个数。
分析:
这题的做法很容易想到,枚举两个点,然后求出正方形另外两个点的坐标,用哈希判断一下是否存在即可(当然也可以排完序后二分)。
思路是简单的,关键是怎么通过正方形的两个点求出另外两点的坐标?可以想到可以枚举正方形的一边或者对角线,其实都可以通过公式得到两点,那么就看怎么求另外两点容易了。我用的是枚举正方形的一条边,然后找出这条边的左右各自的的两点(因为可以和左右各自的两点构成正方形)。用的公式就是下面代码中的getPoint函数的公式,公式画个图就能看出来了。。。
另外看网上还有的旋转点去得到的,就是边长的一点做圆心,另一点旋转90度就可以得到其它点了。可以学习一下。
http://blog.csdn.net/qwb492859377/article/details/47027051
还有这篇:http://blog.csdn.net/viphong/article/details/50527983是枚举的对角线
#include<iostream> #include<cstdio> #include<vector> #include<cstring> #include<algorithm> #include<map> #define x first #define y second using namespace std; const int prime=997; typedef pair<int,int>pii; vector<pii>hs[prime]; pii p[1009]; pii c,d,e,f; void getPoint(pii a,pii b) { c.x=b.x+(b.y-a.y); c.y=b.y-(b.x-a.x); d.x=a.x+(b.y-a.y); d.y=a.y-(b.x-a.x); e.x=b.x-(b.y-a.y); e.y=b.y+(b.x-a.x); f.x=a.x-(b.y-a.y); f.y=a.y+(b.x-a.x); } bool getHash(pii a) { int t=a.x*a.x+a.y*a.y; int id=t%prime; for(int i=0;i<hs[id].size();i++) if(hs[id][i]==a)return true; return false; } int main() { int n,t; while(~scanf("%d",&n)&&n){ for(int i=0;i<prime;i++)hs[i].clear(); for(int i=0;i<n;i++){ scanf("%d%d",&p[i].x,&p[i].y); t=p[i].x*p[i].x+p[i].y*p[i].y; hs[t%prime].push_back(p[i]); } int ans=0; for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ getPoint(p[i],p[j]); if(getHash(c)&&getHash(d))ans++; if(getHash(e)&&getHash(f))ans++; } } printf("%d\n",ans/4); } return 0; }