首页 > 代码库 > poj 2002 Squares
poj 2002 Squares
题目链接：http://poj.org/problem?id=2002
A square is a 4-sided polygon whose sides have equal length and adjacent sides form 90-degree angles. It is also a polygon such that rotating about its centre by 90 degrees gives the same polygon. It is not the only polygon with the latter property, however, as a regular octagon also has this property.
So we all know what a square looks like, but can we find all possible squares that can be formed from a set of stars in a night sky? To make the problem easier, we will assume that the night sky is a 2-dimensional plane, and each star is specified by its x and y coordinates.
Input
Output
题意：二维平面给出一些点，计算以这些点为顶点的正方形的个数。
解法：哈希。因为n为1000，坐标大小高达20000，普通查找肯定不行的，我们得用哈希压缩坐标。
然后枚举正方形的一条边上的两个顶点，可以计算出剩余的两个顶点坐标，然后哈希表查找是否有这样的正方形，统计个数，然后除以4即可（因为枚举了每个正方形的每条边）。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<cmath> 6 #include<algorithm> 7 #define inf 0x7fffffff 8 using namespace std; 9 typedef long long ll;10 const int maxn=1000+10;11 const int mod=100007;12 struct node13 {14 int x,y;15 int next;16 }edge[maxn];17 int head[mod],edgenum;18 int xx[maxn],yy[maxn];19 void insert_hash(int x,int y)20 {21 int k=(x*x+y*y)%mod;22 edge[edgenum].x=x ;23 edge[edgenum].y=y ;24 edge[edgenum].next=head[k] ;25 head[k]=edgenum++ ;26 }27 int search_hash(int x,int y)28 {29 int k=(x*x+y*y)%mod;30 for (int i=head[k] ;i!=-1 ;i=edge[i].next)31 {32 if (x==edge[i].x && y==edge[i].y) return true;33 }34 return false;35 }36 int main()37 {38 int n;39 while (scanf("%d",&n)!=EOF && n)40 {41 memset(head,-1,sizeof(head));42 edgenum=0;43 for (int i=0 ;i<n ;i++)44 {45 scanf("%d%d",&xx[i],&yy[i]);46 insert_hash(xx[i],yy[i]);47 }48 int count=0;49 for (int i=0 ;i<n ;i++)50 {51 for (int j=i+1 ;j<n ;j++)52 {53 int x=xx[i]+(yy[j]-yy[i]);54 int y=yy[i]-(xx[j]-xx[i]);55 int x2=xx[j]-(yy[i]-yy[j]);56 int y2=yy[j]+(xx[i]-xx[j]);57 if (search_hash(x,y) && search_hash(x2,y2)) count ++ ;58 }59 }60 for (int i=0 ;i<n ;i++)61 {62 for (int j=i+1 ;j<n ;j++)63 {64 int x=xx[i]-(yy[j]-yy[i]);65 int y=yy[i]+(xx[j]-xx[i]);66 int x2=xx[j]+(yy[i]-yy[j]);67 int y2=yy[j]-(xx[i]-xx[j]);68 if (search_hash(x,y) && search_hash(x2,y2)) count ++ ;69 }70 }71 printf("%d\n",count/4);72 }73 return 0;74 }
后续：感谢大牛提出宝贵的意见。。。
poj 2002 Squares