poj 2002 Squares 几何二分 || 哈希

Squares

Time Limit: 3500MS		Memory Limit: 65536K
Total Submissions: 15137		Accepted: 5749

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

 1 /*
 2 题意：给你1000个点的坐标(x,y)，让你找出能
 3             构成正方形的个数。
 4 思路：由于是1000，则枚举两个点，求出相应的另外
 5 两个点的坐标。然后用二分判断是否两个点都存在。
 6 
 7 
 8 就个人而言，关键在  "求出相应的另外两个点的坐标"
 9 设两个点a1,a2;
10 由a1为中心，逆时针旋转求出
11 a3.x=a1.y-a2.y+a1.x;
12 a3.y=a2.x-a1.x+a1.y;
13 由a2为中心，顺时针旋转求出
14 a4.x=a1.y-a2.y+a2.x;
15 a4.y=a2.x-a1.x+a2.y;
16 由于被计算两次，所以除2
17 */
18 #include<iostream>
19 #include<stdio.h>
20 #include<cstring>
21 #include<cstdlib>
22 #include<algorithm>
23 using namespace std;
24 
25 typedef struct
26 {
27     int x,y;
28 }node;
29 node a[1003];
30 bool cmp(node n1,node n2)
31 {
32     if( n1.x!=n2.x )
33         return n1.x<n2.x;
34     else return n1.y<n2.y;
35 }
36 bool query(int l,int r,node cur)
37 {
38     int mid;
39     while(l<=r)
40     {
41         mid=(l+r)/2;
42         if( a[mid].x<cur.x || (a[mid].x==cur.x&&a[mid].y<cur.y))
43             l=mid+1;
44         else if( a[mid].x>cur.x || ( a[mid].x==cur.x&&a[mid].y>cur.y))
45             r=mid-1;
46         if( a[mid].x==cur.x && a[mid].y==cur.y) return true;
47     }
48     return false;
49 }
50 int main()
51 {
52     int n,i,j,num;
53     node a1,a2,a3,a4;
54     while(scanf("%d",&n)>0)
55     {
56         if(n==0)break;
57         for(i=1;i<=n;i++)
58             scanf("%d%d",&a[i].x,&a[i].y);
59         sort(a+1,a+1+n,cmp);
60 
61         for(i=1,num=0;i<n;i++)
62         {
63             a1=a[i];
64             for(j=i+1;j<=n;j++)
65             {
66                 a2=a[j];
67                 a3.x=a1.y-a2.y+a1.x;
68                 a3.y=a2.x-a1.x+a1.y;
69                 if( !query(1,n,a3)) continue;
70                 a4.x=a1.y-a2.y+a2.x;
71                 a4.y=a2.x-a1.x+a2.y;
72                 if( query(1,n,a4)) num++;
73 
74             }
75         }
76         printf("%d
",num/2);
77     }
78     return 0;
79 }

哈希做法：

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<algorithm>
 6 using namespace std;
 7 
 8 const int INF = 1000;
 9 typedef struct
10 {
11     int x,y;
12 }node;
13 struct hash
14 {
15     int x;
16     int y;
17     struct hash *next;
18 };
19 struct hash hash_table[1003];
20 node a[INF+3];
21 
22 bool cmp(node n1,node n2)
23 {
24     if( n1.x!=n2.x )
25         return n1.x<n2.x;
26     else return n1.y<n2.y;
27 }
28 void Insert(int x,int y)
29 {
30     unsigned k=(x*x+y*y)%INF;
31     struct hash *new_hash;
32     new_hash=(struct hash *)malloc(sizeof(struct hash));
33     new_hash->x=x;
34     new_hash->y=y;//build 
35 
36     new_hash->next=hash_table[k].next;
37     hash_table[k].next=new_hash;
38 }
39 bool found(int x,int y)
40 {
41     unsigned k=(x*x+y*y)%INF;
42     struct hash *new_hash;
43     new_hash=hash_table[k].next;
44     while(new_hash!=NULL)
45     {
46         if(new_hash->x==x && new_hash->y==y)break;
47         else new_hash=new_hash->next;
48     }
49     if(new_hash==NULL)return false;
50     else return true;
51 }
52 
53 int main()
54 {
55     int n,i,j,num;
56     node a1,a2,a3,a4;
57     while(scanf("%d",&n)>0)
58     {
59         if(n==0)break;
60         memset(hash_table,0,sizeof(hash_table));
61         for(i=1;i<=n;i++)
62         {
63             scanf("%d%d",&a[i].x,&a[i].y);
64             Insert(a[i].x,a[i].y);
65         }
66         sort(a+1,a+1+n,cmp);
67 
68         for(i=1,num=0;i<n;i++)
69         {
70             a1=a[i];
71             for(j=i+1;j<=n;j++)
72             {
73                 a2=a[j];
74                 a3.x=a1.y-a2.y+a1.x;
75                 a3.y=a2.x-a1.x+a1.y;
76                 if(!found(a3.x,a3.y))continue;
77                 a4.x=a1.y-a2.y+a2.x;
78                 a4.y=a2.x-a1.x+a2.y;
79                 if(found(a4.x,a4.y)==true)
80                     num++;
81             }
82         }
83         printf("%d
",num/2);
84     }
85     return 0;
86 }