本文主要是介绍poj 2002 Squares，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：点击打开链接
Description
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.
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
The input consists of a number of test cases. Each test case starts with the integer n (1 <= n <= 1000) indicating the number of points to follow. Each of the next n lines specify the x and y coordinates (two integers) of each point. You may assume that the points are distinct and the magnitudes of the coordinates are less than 20000. The input is terminated when n = 0.
Output
For each test case, print on a line the number of squares one can form from the given stars.
Sample Input
4
1 0
0 1
1 1
0 0
9
0 0
1 0
2 0
0 2
1 2
2 2
0 1
1 1
2 1
4
-2 5
3 7
0 0
5 2
0
Sample Output
1
6
1
题目大意：给出不同的坐标点，问能做成正方形的个数，对于同四个点不同起点的正方形算一个．
基本思路：先定义一个结构体存坐标，压在数学中由知道正方形的两个点就能确定另外两个点可能的位置，这样就只暴力两个点，否则就超时了；
公式：
已知两坐标（x1,y1）(x2,y2)
x3=x1+(y1-y2);y3=y1-(x1-x2);
x4=x2+(y1-y2);y4=y2-(x1-x2);
或：
x3=x1-(y1-y2);y3=y1+(x1-x2);
x4=x2-(y1-y2);y4=y2+(x1-x2);
然后就是hash查找是否存在另外的两点．以前用过hash拉链法，觉的好用就一直用这个（Vector存储的）．对坐标的和hash，将点的序列存进去．
在取余时要注意它的效率问题．
这里定义了两个hash，一个存正数，一个存负数．
因为对每两个点暴力了一下，会用重复的所以最后要除4
<span style="font-size:24px;">#include <iostream>
#define prime 40005
#include<vector>
#include<cstring>
#include<cstdlib>using namespace std;
struct node
{int x,y;
} point[2005];vector<int >hash1[prime],hash2[prime];int search(int x,int y)
{int sum=x+y;if(sum>=0){sum=sum%prime;int len=hash1[sum].size();for(int i=0; i<len; i++){if(x==point[hash1[sum][i]].x&&y==point[hash1[sum][i]].y){return true;}}}else{sum=-1*sum;sum=sum%prime;int len=hash2[sum].size();for(int i=0; i<len; i++){if(x==point[hash2[sum][i]].x&&y==point[hash2[sum][i]].y){return true;}}}return false;
}
int main()
{int n;while(cin>>n,n){for(int i=0; i<prime; i++){hash1[i].clear();hash2[i].clear();}for(int i=0; i<n; i++){cin>>point[i].x>>point[i].y;int sum=point[i].x+point[i].y;if(sum>=0){sum=sum%prime;hash1[sum].push_back(i);}else{sum=-1*sum;sum=sum%prime;hash2[sum].push_back(i);}}int x1,x2,y1,y2,ans=0;for(int i=0; i<n; i++){for(int j=i+1; j<n; j++){if(i==j)continue;x1=point[i].x+(point[i].y-point[j].y);y1=point[i].y-(point[i].x-point[j].x);x2=point[j].x+(point[i].y-point[j].y);y2=point[j].y-(point[i].x-point[j].x);if(search(x1,y1)&&search(x2,y2)){ans++;}x1=point[i].x-(point[i].y-point[j].y);y1=point[i].y+(point[i].x-point[j].x);x2=point[j].x-(point[i].y-point[j].y);y2=point[j].y+(point[i].x-point[j].x);if(search(x1,y1)&&search(x2,y2)){ans++;}}}cout<<ans/4<<endl;}return 0;
}
</span>这篇关于poj 2002 Squares的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
