POJ2002 Squares

【题解】

参考https://blog.csdn.net/ditian1027/article/details/22801635

用散列表存储点的坐标，并采用开散列方法解决关键码冲突。正方形数量计算方法：对于任意两个点，将这两点作为正方形的一条边的两个端点，构造正方形的另外两个点，随后判断这另外两个点是否在点集中即可。值得注意的是，由于每个正方形有四条边，因此最终计算得到的结果应当除以4。

另外，开散列方法创造的链表要在每组数据结束时释放，以避免内存泄漏。

【代码】

  1 #include <iostream>
  2 #include <stack>
  3 using namespace std;
  4 
  5 #define maxp 1005
  6 #define PRIME 21911
  7 #define OUTOFRANGE 0x7fffffff
  8 
  9 struct Point
 10 {
 11     int x;
 12     int y;
 13 }pt[maxp];
 14 
 15 struct hashTab
 16 {
 17     int x;
 18     int y;
 19     hashTab* next;
 20     hashTab() {
 21         x = OUTOFRANGE;
 22         y = OUTOFRANGE;
 23         next = NULL;
 24     }
 25 }ht[PRIME];
 26 
 27 void initHashTab()
 28 {
 29     for (int i = 0; i < PRIME; i++) {
 30         ht[i].x = OUTOFRANGE;
 31         ht[i].y = OUTOFRANGE;
 32         ht[i].next = NULL;
 33     }
 34 }
 35 
 36 void insertHashTab(int x, int y) {
 37     int key = (x * x + y * y) % PRIME;
 38     hashTab *htp = &(ht[key]);
 39     /* Apply open hashing strategy to solve collisions. */
 40     while (htp->next != NULL) htp = htp->next;
 41     htp->x = x;
 42     htp->y = y;
 43     htp->next = new hashTab();
 44 }
 45 
 46 bool pointExist(int x, int y)
 47 {
 48     int key = (x * x + y * y) % PRIME;
 49     hashTab *htp = &(ht[key]);
 50     while (htp->next != NULL) {
 51         if (htp->x == x && htp->y == y)
 52             return true;
 53         htp = htp->next;
 54     }
 55     return false;
 56 }
 57 
 58 void destroyLinkList()
 59 {
 60     hashTab *htp = NULL;
 61     stack<hashTab*> s;
 62     for (int i = 0; i < PRIME; i++) {
 63         htp = &(ht[i]);
 64         while (htp->next != NULL) {
 65             s.push(htp);
 66             htp = htp->next;
 67         }
 68         while (!s.empty()) {
 69             htp = s.top();
 70             delete (htp->next);
 71             s.pop();
 72         }
 73     }
 74 }
 75 
 76 int main()
 77 {
 78     int n, x, y;
 79     while (cin >> n) {
 80         if (n == 0)break;
 81         long cnt = 0;
 82         initHashTab();
 83         for (int i = 0; i < n; i++) {
 84             cin >> x >> y;
 85             insertHashTab(x, y);
 86             pt[i].x = x;
 87             pt[i].y = y;
 88         }
 89         for (int i = 0; i < n; i++)
 90             for (int j = i + 1; j < n; j++) {
 91                 int dx = pt[j].x - pt[i].x;
 92                 int dy = pt[j].y - pt[i].y;
 93                 int x1 = pt[i].x - dy;
 94                 int y1 = pt[i].y + dx;
 95                 int x2 = x1 + dx;
 96                 int y2 = y1 + dy;
 97                 if (pointExist(x1, y1) && pointExist(x2, y2))
 98                     cnt++;
 99                 int x3 = pt[i].x + dy;
100                 int y3 = pt[i].y - dx;
101                 int x4 = x3 + dx;
102                 int y4 = y3 + dy;
103                 if (pointExist(x3, y3) && pointExist(x4, y4))
104                     cnt++;
105             }
106         cnt /= 4;
107         printf("%ld
", cnt);
108         destroyLinkList();
109     }
110     return 0;
111 }