POJ 2002 Squares 哈希

题目链接： http://poj.org/problem?id=2002
 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 const int prime = 999983;
 5 
 6 struct Hash_table
 7 {
 8     int x, y;
 9     struct Hash_table *next;
10 }*Hash[prime];
11 
12 void Hash_insert(int x, int y)
13 {
14     int key = (x + y) % prime;
15     if(Hash[key] == NULL)
16     {
17         Hash[key] = new Hash_table;
18         Hash[key]->x = x;
19         Hash[key]->y = y;
20         Hash[key]->next = NULL;
21         return;
22     }
23     struct Hash_table *p = Hash[key];
24     
25     //必须注意！下面几行一定是p->next，如果改成：
26     /*
27     while(p != NULL)
28         p = p->next;
29     p = new Hash_table;
30     p->x = x;
31     p->y = y;
32     p->next = NULL;
33     */
34     //是绝对不行的，因为这里调试了半天了。。。。。。
35     //正解如下：
36     while(p->next != NULL)
37         p = p->next;
38     p->next = new Hash_table;
39     p->next->x = x;
40     p->next->y = y;
41     p->next->next = NULL;
42 }
43 
44 bool Hash_search(int x, int y)
45 {
46     int key = (x + y) % prime;
47     struct Hash_table *p = Hash[key];
48     while(p != NULL)
49     {
50         if(p->x == x && p->y == y)
51             return 1;
52         p = p->next;
53     }
54     return 0;
55 }
56 
57 int main()
58 {
59     int n, tx, ty, x[1010], y[1010];
60     int x3, x4, y3, y4;
61     while(scanf("%d", &n) != EOF && n)
62     {
63         memset(Hash, 0, sizeof(Hash));
64         for(int i = 0; i < n; i++)
65         {
66             scanf("%d %d", &tx, &ty);
67             x[i] = tx + 20000;
68             y[i] = ty + 20000;
69             Hash_insert(x[i], y[i]);
70         }
71         int ans = 0;
72         for(int i = 0; i < n; i++)
73         {
74             for(int j = 0; j < n; j++)
75             {
76                 if(j == i)continue;
77                 x3 = x[i]+(y[i]-y[j]);
78                 y3 = y[i]-(x[i]-x[j]);
79                 x4 = x[j]+(y[i]-y[j]);
80                 y4 = y[j]-(x[i]-x[j]);
81                 if(Hash_search(x3, y3) && Hash_search(x4, y4))
82                     ans++;
83             }
84         }
85         printf("%d
", ans/4);
86     }
87     return 0;
88 }
View Code