题目描述
正方形是边长相等且相邻边形成90度角的4边多边形。它也是一个多边形，围绕其中心旋转 90 度会得到相同的多边形。然而，它不是唯一具有后一特性的多边形，因为正八边形也具有此特性。
所以我们都知道正方形是什么样子的，但是我们能找到所有可能由夜空中的一组星星组成的正方形吗？为了使问题更容易，我们假设夜空是一个二维平面，每颗星星都由它的 x 和 y 坐标指定。
输入
输入由许多测试用例组成。每个测试用例以整数 n (1 <= n <= 1000) 开始，表示要跟踪的点数。接下来的 n 行中的每一行都指定了每个点的 x 和 y 坐标（两个整数）。您可以假设点是不同的，并且坐标的大小小于 20000。当 n = 0 时，输入终止。
输出
对于每个测试用例，在一行上打印一个人可以从给定的星星形成的正方形数。
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
思路分析
题目分析:直接将四个点枚举会超时,所以任意枚举两个点,将任意两个点算出来后判断是否在自己创建的hash表中.可以按照什么规则呢?如下图所示,我们把两个点当成相邻边的点,我们可以算出其他两个点的坐标.
假设x1,x2,x3,x4的输入顺序是x1,x2,x3,x4则在进行枚举时(先以右上正方形为例)对于一个正方形会被ans++四次.
i-->x1;j-->x2; i-->x1;j-->x4; i-->x2;j-->x3; i-->x3;j-->x4
当枚举到这四种情况时,都可以在hashTab中找到该正方形的其他两点,并且这四种情况对应的是同一个正方形.
同理左下正方形也是这个规律.
所以最终结果ans要 / 4;
参考代码
//POJ2002 #include<iostream> using namespace std; const int N=1010; const int H=10007; int ptx[N],pty[N]; struct Node{ int x; int y; int next; }; Node node[N]; int cur;//控制当前静态链表的下标的 int n; long ans;//统计数目 int hashTab[H]; void initHash() //这里不能使用memset因为这个仅对字符数组有效 { for(int i = 0;i<H;i++){ hashTab[i] = -1; } cur = 0; ans = 0; } void insertHash(int x,int y){ int h = (x*x+y*y)%H; //Hash函数计算地址 node[cur].x = x; node[cur].y = y; node[cur].next = hashTab[h];//采用前插法 hashTab[h] = cur; cur++; } int searchHash(int x,int y) { int h = (x*x+y*y) % H; int next; next = hashTab[h]; while(next!=-1){ if(x==node[next].x&&y==node[next].y){ return 1; } next = node[next].next; } return 0; } int main() { while(cin>>n&&n){ initHash(); for(int i = 0;i<n;i++) { scanf("%d%d",&ptx[i],&pty[i]); insertHash(ptx[i],pty[i]); } for(int i = 0; i< n;i++){ for(int j = i+1;j<n;j++){ int x3 = ptx[j]+(pty[i]-pty[j]); int y3 = pty[j]+(ptx[j]-ptx[i]); int x4 = ptx[i]+(pty[i]-pty[j]); int y4 = pty[i]+(ptx[j]-ptx[i]); if(searchHash(x3,y3)&&searchHash(x4,y4)){ ans++; } } } for(int i = 0; i< n;i++){ for(int j = i+1;j<n;j++){ int x3 = ptx[j]-(pty[i]-pty[j]); int y3 = pty[j]-(ptx[j]-ptx[i]); int x4 = ptx[i]-(pty[i]-pty[j]); int y4 = pty[i]-(ptx[j]-ptx[i]); if(searchHash(x3,y3)&&searchHash(x4,y4)){ ans++; } } } ans>>=2; printf("%ld\n",ans); } return 0; }
注意:本题使用线性探测法会出现多个数据堆积,然后运行超时.
