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求正方形个数,布布扣,bubuko.com

POJ 2002 Squares hash求正方形个数

原文：http://blog.csdn.net/u011686226/article/details/22942729