poj2002 -- 点的hash

题目：

Squares

Time Limit: 3500MS		Memory Limit: 65536K
Total Submissions: 15261		Accepted: 5792

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

Sample Output

1
6
1

Source

Rocky Mountain 2004

大意：给出n个点的坐标求能组成多少个正方形。

思路：

依次枚举两个点，求出另外点的坐标，看看另外能组成正方形的点是否存在。

已知两点A（x1，y1）B（x2，y2）

则另外两点的坐标：

x3=x1+|y1-y2|;

y3=y1-|x1-x2|;

x4=x2+|y1-y2|;

y2=y2-|x1-x2|;

最难的部分便是对点的储存了 ,

这里先给出点储存的模板，通过hash数组和next数组的转换达到储存点的目的：

code：

 1 struct point
 2 {
 3     int x;
 4     int y;
 5 }poin[maxn];
 6 
 7 int hash[maxn+10];
 8 int next[maxn+10];
 9 
10 int findkey(point p)
11 {
12     return abs(p.x+p.y)%maxn;
13 }
14 
15 void hashinsert(int i)
16 {
17     int key=findkey(poin[i]);
18     next[i]=hash[key];//最后一个next储存的是-1，其他的都指向下一个next
19     hash[key]=i;//指向最开头的next的下标
20 }
21 
22 int hashsearch(point p)
23 {
24     int key=findkey(p);
25     int i=hash[key];
26     while(i!=-1)
27     {
28         if(p.x==poin[i].x&&p.y==poin[i].y)//找到一个这样的点
29         return 1;
30         i=next[i];
31     }
32     return 0;
33 }

题目代码：

 1 #include<iostream>
 2 #include<string.h>
 3 #include<stdio.h>
 4 #include<algorithm>
 5 #include<math.h>
 6 using namespace std;
 7 
 8 const int maxn=1031;
 9 
10 struct point
11 {
12     int x;
13     int y;
14 }poin[maxn];
15 
16 int hash[maxn+10];
17 int next[maxn+10];
18 
19 int findkey(point p)
20 {
21     return abs(p.x+p.y)%maxn;
22 }
23 
24 void hashinsert(int i)
25 {
26     int key=findkey(poin[i]);
27     next[i]=hash[key];
28     hash[key]=i;
29 }
30 
31 int hashsearch(point p)
32 {
33     int key=findkey(p);
34     int i=hash[key];
35     while(i!=-1)
36     {
37         if(p.x==poin[i].x&&p.y==poin[i].y)
38         return 1;
39         i=next[i];
40     }
41     return 0;
42 }
43 
44 
45 bool cmp(point p1,point p2)
46 {
47     if(p1.x!=p2.x)
48     return p1.x<p2.x;
49     else
50     return p1.y<p2.y;
51 }
52 
53 int main()
54 {
55     int n;
56     int x1,x2,x3,x4;
57     int y1,y2,y3,y4;
58     //freopen("aa.txt","r",stdin);
59     while(scanf("%d",&n)!=EOF)
60     {
61         if(n==0)
62         break;
63         memset(hash,-1,sizeof(hash));
64         memset(next,-1,sizeof(next));
65         point p3,p4;
66         for(int i=0;i<n;i++)
67             scanf("%d%d",&poin[i].x,&poin[i].y);
68         sort(poin,poin+n,cmp);
69         for(int i=0;i<n;i++)
70             hashinsert(i);
71         int ans=0;
72         for(int i=0;i<n;i++)
73         {
74             for(int j=i+1;j<n;j++)
75             {
76                 x1=poin[i].x;
77                 y1=poin[i].y;
78                 x2=poin[j].x;
79                 y2=poin[j].y;
80                 p3.x=x1+(y2-y1);
81                 p3.y=y1-(x2-x1);
82                 p4.x=x2+(y2-y1);
83                 p4.y=y2-(x2-x1);
84                 if(hashsearch(p3)&&hashsearch(p4))
85                 ans++;
86             }
87         }
88         printf("%d
",ans/2);
89     }
90     return 0;
91 }

View Code