先将点排序，外层 x 递增，选定最左端点 p1 后第二层循环寻找右端点 p2，从而确定对角线投影在 x, y 上的长度，根据这个确定另外两个点坐标，二分搜索 p1 到 p2 之间的点。
注意以下几点：
将所有输入的坐标值乘 2，确保在计算另两个点的时候得到整数。
将 x 坐标的第一个元素的索引单独储存起来，方便按 x 递增。
注意二分搜索的范围只在 p1 到 p2 之间，即提高效率，也避免重复。

#include <cstdio>
#include <algorithm>
using namespace std;

#define MAXN 1000

typedef pair<int, int> P;

P _ns[MAXN];
int _xs[MAXN + 1];
int _n, _x, _res;

int Ipt()
{
	if (scanf("%d", &_n), !_n)
	{
		return EOF;
	}
	_x = 0, _res = 0;
	int i, f, s;
	for (i = 0; i < _n; ++i)
	{
		scanf("%d%d", &f, &s);
		_ns[i].first = (f << 1);    // 坐标翻倍
		_ns[i].second = (s << 1);
	}
	sort(_ns, _ns + _n);
	int preX = _ns[0].first;
	_xs[_x++] = 0;
	for (i = 1; i < _n; ++i)    // 储存 x 索引
	{
		if (_ns[i].first != preX)
		{
			_xs[_x++] = i;
			preX = _ns[i].first;
		}
	}
	_xs[_x] = _n;
	return 0;
}

inline void Opt()
{
	printf("%d\n", _res);
}

void Test()
{
	int i, j, k;
	int jEnd;
	int x1, x2, x3, x4, y1, y2, y3, y4;
	int xMid, yMid, xSub, ySub;
	P *p = NULL, *pEnd = NULL;
	bool flag = false;
	for (i = 0; i < _x; ++i)
	{
		jEnd = _xs[i + 1];
		for (j = _xs[i]; j < jEnd; ++j)
		{
			x1 = _ns[j].first;
			y1 = _ns[j].second;
			for (k = i + 1; k < _x; ++k)
			{
				p = _ns + _xs[k], pEnd = _ns + _xs[k + 1];
				while (p != pEnd)
				{
					x2 = p->first;
					y2 = p->second;
					xSub = (x2 - x1) / 2;
					xMid = x1 + xSub;
					yMid = (y1 + y2) / 2;
					ySub = (y2 - y1) / 2;
					x3 = xMid - ySub;
					y3 = yMid + xSub;
					x4 = xMid + ySub;
					y4 = yMid - xSub;
					if (binary_search(_ns + j + 1, p, P(x3, y3)) 
						&& binary_search(_ns + j + 1, p, P(x4, y4)))    // 注意搜索范围
					{
						++_res;
					}
					++p;
				}
			}
		}
	}
}

int main()
{
	while (EOF != Ipt())
	{
		Test();
		Opt();
	}
	return 0;
}
 2002 Squares (216K 1141MS)

• 这思路很不错.... (0) inowfordream 2009-07-15 20:38:39