bzoj1069: [SCOI2007]最大土地面积

1、O(N^2)地枚举对角线。

2、分别求出这条对角线左右两侧到这条线段所在直线距离最大的点，记为l、r，相当于求出以这条对角线为底、左右两侧分别高最大（面积最大）的三角形。

3、对于枚举的每条对角线，计算四边形面积并更新答案。

这样的时间复杂度是O(N^3)的，不能承受，一个优化就是，可以证明：如果按照逆时针顺序存储凸包，那么对于对角线(i,j+1)，与之相对应的l、r分别在对角线(i,j)的逆时针方向，也就是说可以省略一些不必要的枚举过程。对于对角线(i,j+1)的l、r，可以直接从对角线(i,j)的l、r开始枚举。

传送门：http://hi.baidu.com/poet_shy/item/dcda39d1dfa538262a35c751

const int N = 2010;
const DB Eps = 1e-8;
struct Node {
	DB Ox, Oy;
	
	Node() {}
	Node(DB _Ox, DB _Oy) : Ox(_Ox), Oy(_Oy) {}
	inline DB operator *(Node A) { return Ox * A.Oy - Oy * A.Ox; }
	inline bool operator <(const Node &A) const { return A.Oy == Oy ? Ox < A.Ox : Oy < A.Oy; }
	inline Node operator +(Node A) { return Node(Ox +  A.Ox, Oy + A.Oy); }
	inline Node operator -(Node A) { return Node(Ox - A.Ox, Oy - A.Oy); }
} Dat[N], Q[N << 1];
int Stack[N << 1], Top, n;
bool Vis[N];
DB Ans;

inline void Input() {
	scanf("%d", &n);
	For(i, 1, n) scanf("%lf%lf", &Dat[i].Ox, &Dat[i].Oy);
}

inline int Sign(DB T) {
	if(fabs(T) < Eps) return 0;
	return T < 0 ? -1 : 1;
}

inline void Work(int s) {
	int u = s + 1, d = s + 3;
	For(i, s + 2, s + n - 2) {
		while(u + 1 < i && fabs((Q[s] - Q[i]) * (Q[u] - Q[i])) < fabs((Q[s] - Q[i]) * (Q[u + 1] - Q[i]))) u++;
		while(d + 1 <= s + n - 1 && fabs((Q[s] - Q[i]) * (Q[d] - Q[i])) < fabs((Q[s] - Q[i]) * (Q[d + 1] - Q[i]))) d++;
		Ans = max(Ans, fabs((Q[s] - Q[i]) * (Q[u] - Q[i])) + fabs((Q[s] - Q[i]) * (Q[d] - Q[i])));
	}
}
inline void Solve() {
	sort(Dat + 1, Dat + n + 1);
	For(i, 1, n) {
		while(Top > 1 
			&& (Sign((Dat[i] - Dat[Stack[Top - 1]]) * (Dat[Stack[Top]] - Dat[Stack[Top - 1]])) >= 0)) Vis[Stack[(--Top) + 1]] = 0;
		Vis[Stack[++Top] = i] = 1;
	}
	int T = Top - 1;
	Vis[1] = 0;
	Ford(i, n - 1, 1)
		if(!Vis[i]) {
			while(Top - T > 1 && 
				(Sign((Dat[i] - Dat[Stack[Top - 1]]) * (Dat[Stack[Top]] - Dat[Stack[Top - 1]])) >= 0)) --Top;
			Stack[++Top] = i;
		}
	n = --Top, Ans = 0;
	For(i, 1, Top) Q[i] = Q[i + Top] = Dat[Stack[i]];
	For(i, 1, n) Work(i);
	printf("%.3lf\n", Ans / 2.0);
}

int main() {
	#ifndef ONLINE_JUDGE
	SETIO("1069");
	#endif
	Input();
	Solve();
	return 0;
}