POJ 2002 Squares hash求正方形个数

本文主要是介绍POJ 2002 Squares hash求正方形个数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：给你n个点 坐标都小于20000 数一下可以组成多少个正方形

思路：借鉴了网上hash的思路 哈希链地址法 把x+y的绝对值相同的放人一个链表里 然后枚举2个点（1条边上的） 推算出另外2个点

另外2点分别是

x1 = a[i].x+(a[i].y-a[j].y);y1 = a[i].y-(a[i].x-a[j].x);

x2 = a[j].x+(a[i].y-a[j].y);y2 = a[j].y-(a[i].x-a[j].x); i ,j 是枚举的2个点的下标

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std;
const int maxn = 40010;
int next[maxn], first[maxn];
struct point
{int x, y;
}a[1010];
bool cmp(point a, point b)
{if(a.x != b.x)return a.x < b.x;return a.y < b.y;
}
bool ok(int x, int y)
{int sum = abs(x+y);for(int i = first[sum]; i != -1; i = next[i]){if(a[i].x == x && a[i].y == y)return true;}return false;
}
int main()
{int n;while(scanf("%d", &n) && n){memset(next, -1, sizeof(next));memset(first, -1, sizeof(first));for(int i = 0; i < n; i++){scanf("%d %d", &a[i].x, &a[i].y);}sort(a, a+n, cmp);for(int i = 0; i < n; i++){int sum = abs(a[i].x + a[i].y);next[i] = first[sum];first[sum] = i;}int ans = 0;for(int i = 0; i < n; i++){for(int j = i+1; j < n; j++){int x = a[i].x+(a[i].y-a[j].y);int y = a[i].y-(a[i].x-a[j].x);if(!ok(x, y))continue;x = a[j].x+(a[i].y-a[j].y);y = a[j].y-(a[i].x-a[j].x);if(ok(x, y))ans++;}}printf("%d\n", ans/2);}return 0;
}

 

 

这篇关于POJ 2002 Squares hash求正方形个数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---