POJ 2079 Triangle (凸包&旋转卡壳)

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

O(N^3)枚举肯定不行，但是我们换个思路，可以得到一个O(3N)的线性“枚举”算法（旋转卡壳）

怎么做？

令i=0,j=1,k=2，这是我们最开始的三角形，然后不断放大这个三角形：先放大k至面积最大，再放大j至面积最大，再放大i至面积最大。由于叉积的良好性质，在放大的过程中保证i<j<k。这样因为每个点至多被经过3次，所以复杂度是O(3N)的。

/*47ms,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 RC()
{
	ans[len] = ans[0];
	int ret = 0, tmp;
	for (int i = 0, j = 1, k = 2; i < len; ++i)
	{
		while ((tmp = (ans[j] - ans[i]).det(ans[k] - ans[i])) < (ans[j] - ans[i]).det(ans[k + 1] - ans[i]))
			k = (k + 1) % len;
		while ((tmp = (ans[j] - ans[i]).det(ans[k] - ans[i])) < (ans[j + 1] - ans[i]).det(ans[k] - ans[i]))
			j = (j + 1) % len;
		ret = max(ret, tmp);
	}
	return ret;
}

int main()
{
	int i, j, k, mxarea;
	while (scanf("%d", &n), n > 0)
	{
		for (i = 0; i < n; ++i) p[i].read();
		if (n < 3)
		{
			puts("0.00");
			continue;
		}
		convex_hull();
		mxarea = RC();
		if (mxarea & 1) printf("%d.50\n", mxarea >> 1);
		else printf("%d.00\n", mxarea >> 1);
	}
	return 0;
}

POJ 2079 Triangle (凸包&旋转卡壳)

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