POJ1971 Parallelogram Counting(hash)

题意：

给出一系列点的坐标，要求能组成几个不同的平行四边形。

要点：

思路很简单，找两个点的中点组成哈希表即可，我用链表写不是超时就是超空间，看来ACM还是尽量别用指针，用数组模拟链表可过。

#include<iostream>
using namespace std;
const int hashnum = 7345787;
int head[hashnum], nextnode[1000003];
int ans,m;struct points
{int x, y;
}point[1005];
struct midpoints
{int x, y, cnt;
}midpoint[1000003];int HashFunction(int x, int y) 
{int h;h = ((x << 2) + (x >> 4)) ^ (y << 10);h = h % hashnum;h = h < 0 ? h + hashnum : h;return h;
}
void HashInsert(int x, int y)
{int h = HashFunction(x, y);bool flag = false;for (int i = head[h]; i != -1; i = nextnode[i]){if (midpoint[i].x == x&&midpoint[i].y == y){flag = true;ans += midpoint[i].cnt++;}}if (!flag){midpoint[m].x = x;midpoint[m].y = y;midpoint[m].cnt = 1;nextnode[m] = head[h];//用数组模拟链表，倒序插入head[h] = m++;}}int main()
{int t, n;cin >> t;while (t--){cin >> n;ans = m = 0;memset(head, -1, sizeof(head));for (int i = 0; i < n; i++)cin >> point[i].x >> point[i].y;for(int i=0; i<n; i++)for (int j = i+1; j < n; j++){int x = point[i].x + point[j].x;int y = point[i].y + point[j].y;HashInsert(x, y);}cout << ans << endl;}return 0;
}