POJ 2187 Beauty Contest (凸包&最远点距)

http://poj.org/problem?id=2187

思路：算出凸包后枚举凸包上的点。复杂度为O(NlogN+M)

为什么可以枚举？

设坐标的绝对值不超过M，则凸包至多有O(√M)个顶点

证明：以(0,0)为起点画出如下“极限凸包”

(0,0)-(1,0)-(2,1)-(3,3)-(4,6)-...当x每次只增加1时，y增加速率是平方级的，所以凸包至多有O(√M)个顶点。

/*79ms,1140KB*/

#include<cstdio>
#include<algorithm>
using namespace std;
const int mx = 50005;

struct P
{
	int x, y;
	P(int x = 0, int y = 0): x(x), y(y) {}
	void read()
	{
		scanf("%d%d", &x, &y);
	}
	P operator - (P& p)
	{
		return P(x - p.x, y - p.y);
	}
	bool operator < (const P& p) const///加cosnt以便sort调用，其他函数不加const对速度没有影响
	{
		return x < p.x || x == p.x && y < p.y;
	}
	int dot(P p)
	{
		return x * p.x + y * p.y;
	}
	int det(P p)
	{
		return x * p.y - y * p.x;
	}
};

P p[mx], ans[mx];
int n, len;

///求凸包
void convex_hull()
{
	sort(p, p + n);
	len = 0;
	int i;
	for (i = 0; i < n; ++i)
	{
		while (len >= 2 && (ans[len - 1] - ans[len - 2]).det(p[i] - ans[len - 1]) <= 0)
			--len;
		ans[len++] = p[i];
	}
	int tmp = len;
	for (i = n - 2; i >= 0; --i)
	{
		while (len > tmp && (ans[len - 1] - ans[len - 2]).det(p[i] - ans[len - 1]) <= 0)
			--len;
		ans[len++] = p[i];
	}
	--len;
}

int main()
{
	int i, j;
	scanf("%d", &n);
	for (i = 0; i < n; ++i) p[i].read();
	convex_hull();
	int mxdis = 0;
	for (i = 1; i < len; ++i)
		for (j = 0; j < i; ++j)
			mxdis = max(mxdis, (ans[i] - ans[j]).dot(ans[i] - ans[j]));
	printf("%d\n", mxdis);
	return 0;
}

POJ 2187 Beauty Contest (凸包&最远点距)

原文：http://blog.csdn.net/synapse7/article/details/19193701