| Time Limit: 3500MS | Memory Limit: 65536K | |
| Total Submissions: 14328 | Accepted: 5393 |
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.
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
题意：给出n个点的坐标，计算这些点可以构成多少个正方形，不同顺序的相同四个点被视为同一个正方形。 思路：这里n最大是1000，显然一个点一个点的枚举不行。参考了别人的结题报告，据说有这样的定理：
已知（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);
因此可以先枚举两个点，根据这两个点（点1 ，点2）的坐标可以得到另外两个点（点3， 点4），若在哈希表中能找得到这两个（点3， 点4），说明能构成一个正方形，
注意每个点被枚举了四次，最后要除以4；
再者就是找哈希函数，这里用的平方取余法，每输入一个点，就将这个点插入哈希表中；
这个题也受了 poj 3274的启发；
#include<stdio.h>
#include<string.h> const int prime = ;
struct node
{
int x,y;
}pos[]; struct HashTable
{
int x;
int y;
struct HashTable* next;
}*Hash[prime];//Hash[]是指针数组，存放地址；
int n; //插入哈希表
void hash_insert(int x, int y)
{
int key = (x*x + y*y)%prime;//平方求余法；
if(!Hash[key])
{
Hash[key] = new struct HashTable;
Hash[key]->x = x;
Hash[key]->y = y;
Hash[key]->next = NULL;
}
else
{
struct HashTable *tmp = Hash[key];
while(tmp->next)
tmp = tmp->next;//开放寻址，直到next为空
//插入新结点
tmp->next = new struct HashTable;
tmp->next->x = x;
tmp->next->y = y;
tmp->next->next = NULL;
}
}
bool find(int x, int y)
{
int key = (x*x+y*y)%prime;
if(!Hash[key])
return false;//key 对应的地址不存在，
else
{
struct HashTable *tmp = Hash[key];
while(tmp)
{
if(tmp->x == x && tmp->y == y)
return true;
tmp = tmp->next;
}
return false;
}
}
int main()
{
while(scanf("%d",&n)!= EOF)
{
int i,j;
if(n == ) break;
memset(Hash,,sizeof(Hash));
for(i = ; i < n; i++)
{
scanf("%d %d",&pos[i].x,&pos[i].y);
hash_insert(pos[i].x, pos[i].y);
}
int ans = ;
for(i = ; i < n-; i++)
{
for(j = i+; j < n; j++)
{
int x1 = pos[i].x, y1 = pos[i].y;
int x2 = pos[j].x, y2 = pos[j].y;
int add_x = x1-x2,add_y = y1-y2;
int x3 = x1+add_y;
int y3 = y1-add_x;
int x4 = x2+add_y;
int y4 = y2-add_x;
if(find(x3,y3) && find(x4,y4))
ans++; x3 = x1-add_y;
y3 = y1+add_x;
x4 = x2-add_y;
y4 = y2+add_x;
if(find(x3,y3) && find(x4,y4))
ans++;
}
}
printf("%d\n",ans/);
}
return ;
}