poj 2002 二分查找，hash

算法过程：

1 将顶点按x坐标递增排序，若x相同，按y坐标递增排序，然后枚举所有边，对每一条由点p1和p2(根据排序p1 < p2)组成的边按照如下方式可唯一确定一个正方形：

    1) 将边绕p1逆时针旋转90度得到点p3

    2) 将边绕p2顺时针旋转90度得到点p4

则p1 p2 p3 p4组成一个正方形，设p1 = (x1,y1), p2 = (x2, y2)，根据向量的旋转公式可以求出p3, p4的坐标为

p3 = (y1 - y2 + x1, x2 - x1 + y1)

p4 = (y1 - y2 + x2, x2 - x1 + y2)

 

2 然后搜索点p3和p4是否存在，若存在则找到一个正方形，计数加1，可以发现总是存在两条边确定的正方形是一样的，也就是说每个正方形会被发现2次，所以要将最后的计数结果除以2.

 

实现的时候关键是如何搜索某个点是否存在，由于所有点都排序过，所以可以用二分查找来搜索，但速度比较慢，至少1000ms， hash的速度更快些，可以达到几百ms，还有hash表如果用开放地址线性探测法解决冲突的话，很容易超时，

而用链地址法解决冲突效果要好很多。下面是二分搜索和hash两种方法的代码实现。

 

二分查找

 

#include <stdio.h>
#include <string.h>

//#define DEBUG

#ifdef DEBUG
#define debug(...) printf( __VA_ARGS__) 
#else
#define debug(...)
#endif

#define N 1000

struct Point {
	int x;
	int y;
};

struct Point point[N];

int n;	/* 点的个数 */

/* 由于点已经按照坐标排序过，所以采用二分查找
 * 搜索点(x,y)是否存在，存在返回1，否则返回0
 */
int bsearch(int x, int y)
{
	int		m, s, t;

	s = 0;
	t = n-1;
	while (s <= t) {
		m = (s+t)/2;
		if (point[m].x == x && point[m].y == y) return 1;
		if (point[m].x > x || (point[m].x == x && point[m].y > y)) {
			t = m-1;
		}
		else {
			s = m+1;
		}
	}
	return 0;
}

int main()
{
	int 	x, y, i, j, count;

	while (scanf("%d", &n), n) {
		count = 0;
		for (i = 0; i < n; i++) {
			scanf("%d %d", &x, &y);
			//插入法对点排序，按照x从小到大，y从小到大，且x优先排列的方式
			for (j = i-1; j >= 0; j--) {
				if (point[j].x > x || (point[j].x == x && point[j].y > y)) {
					point[j+1] = point[j];
				} else {
					break;
				}
			}
			point[j+1].x = x;
			point[j+1].y = y;
		}
		/* 枚举所有边，对每条边的两个顶点可以
		 * 确定一个唯一的正方形，并求出另外两个顶点的坐标
		 */
		for (i = 0; i < n; i++) {
			for (j = (i+1); j < n; j++) {
				//计算第三个点的坐标，搜索其是否存在
				x = point[i].y-point[j].y+point[i].x;
				y = point[j].x-point[i].x+point[i].y;
				if (bsearch(x,y) == 0) {
					continue;
				}
				//计算第四个点的坐标，搜索其是否存在
				x = point[i].y-point[j].y+point[j].x;
				y = point[j].x-point[i].x+point[j].y;
				if (bsearch(x, y)) {
					count++;
				}
			}
		}
		printf("%d\n", count/2);
	}
	return 0;
}

 

hash

 

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define DEBUG

#ifdef DEBUG
#define debug(...) printf( __VA_ARGS__) 
#else
#define debug(...)
#endif

#define N 1000	/* 顶点个数 */
#define M 2999	/* hash表的大小，取素数冲突冲突较少 */

struct Point {
	int x;
	int y;
};

struct Point point[N];

/* 使用链地址法解决冲突, 表头不存数据 */
struct hash_entry {
	int x;
	int y;
	struct hash_entry *next;
};

struct hash_entry hash_table[M+1];

int conflict;

void insert(int x, int y) 
{
	unsigned int 	p;
	struct hash_entry *new_entry;

	p = (x*x+y*y)%M;	/* hash函数 */
	//创建一个新的entry
	new_entry = (struct hash_entry *)malloc(sizeof(struct hash_entry));
	new_entry->x = x;
	new_entry->y = y;
	/* 把新entry插在最前面，这样，越先插进来的entry在链表的越后面，
	 *最后一个entry的next指针为空
	 */
	new_entry->next = hash_table[p].next;
	hash_table[p].next = new_entry;
}


int find(int x, int y)
{
	unsigned int 	p;
	struct hash_entry *entry;

	p = (x*x+y*y)%M;	/* hash函数 */
	for(entry = hash_table[p].next; entry != 0 && (entry->x != x \
				|| entry->y != y); entry = entry->next, conflict++);	
	if (entry) {
		return 1;
	}
	return 0;
}

int main()
{
	int 	n, x, y, i, j, count;

	while (scanf("%d", &n), n) {
		memset(hash_table, 0, sizeof(hash_table));
		count = 0;
		for (i = 0; i < n; i++) {
			scanf("%d %d", &x, &y);
			//插入法对点排序，按照x从小到大，y从小到大，且x优先排列的方式
			for (j = i-1; j >= 0; j--) {
				if (point[j].x > x || (point[j].x == x && point[j].y > y)) {
					point[j+1] = point[j];
				} else {
					break;
				}
			}
			point[j+1].x = x;
			point[j+1].y = y;
			insert(x, y);
		}
		/* 枚举所有边，对每条边的两个顶点可以
		 * 确定一个唯一的正方形，并求出另外两个顶点的坐标
		 */
		for (i = 0; i < n; i++) {
			for (j = (i+1); j < n; j++) {
				//计算第三个点的坐标，搜索其是否存在
				x = point[i].y-point[j].y+point[i].x;
				y = point[j].x-point[i].x+point[i].y;
				if (!find(x, y)) {
					continue;
				}
				//计算第四个点的坐标，搜索其是否存在
				x = point[i].y-point[j].y+point[j].x;
				y = point[j].x-point[i].x+point[j].y;
				if (find(x, y)) {
					count++;
				}
			}
		}
		printf("%d\n", count/2);
	}
	debug("conflict = %d\n", conflict);
	return 0;
}