HDU6219 Empty Convex Polygons

求最大空凸包（即凸包内部没有其他点）

Solution

枚举凸包最下方的点，设为 $O$，将其他 $y$ 值大于它的点按极角序排序。设 $dp[i][j]$ 表示以 $P_i\rightarrow O,P_j\rightarrow P_i$ 为凸包最后两条边的最大空凸包面积，则 $dp[i][j]=\max(S_{\Delta OP_iP_j}+dp[j][k])$，其中 $i,j,k$ 要满足空凸包的条件。

由于可能有共线的情况，这个条件写起来还是要小心的。首先要保证 $OP_j$ 与 $OP_i$ 不共线，然后保证 $\Delta OP_iP_j$ 内部没有其他点，然后保证没有和 $P_j$ 极角相同距离却更小的点（容易漏掉），最后 $\overrightarrow{P_jP_i}$ 要在 $\overrightarrow{P_kP_i}$ 转左。

复杂度：$O(n^4)$

Code

#include<bits/stdc++.h>

using namespace std;

const double eps = 1e-8;
const double PI = acos(-1);
const double INF = 1e16;
inline int sgn(double x){
    if(fabs(x) < eps)	return 0;
    else if(x > 0)	return 1;
    else	return -1;
}
inline int cmp(double x, double y){
    if(fabs(x-y) < eps)	return 0;
    else if(x > y)	return 1;
    else	return -1;
}

struct Vector{
    double x, y, ang;
    Vector(double x = 0, double y = 0):x(x), y(y){}
    void read(){ scanf("%lf%lf", &x, &y); }
};
typedef Vector Point;
Vector operator + (Vector A, Vector B){ return Vector{A.x + B.x, A.y + B.y}; }
Vector operator - (Vector A, Vector B){ return Vector{A.x - B.x, A.y - B.y}; }
Vector operator * (double k, Vector A){ return Vector{k * A.x, k * A.y}; }
bool operator < (const Vector &A, const Vector &B){ return cmp(A.x, B.x) == 0 ? cmp(A.y, B.y) < 0 : cmp(A.x, B.x) < 0; }
double operator * (Vector A, Vector B){ return A.x * B.x + A.y * B.y; } // dot product
double operator ^ (Vector A, Vector B){ return A.x * B.y - A.y * B.x; } // cross product
double Length(Vector A){ return sqrt(A * A); }
double Angle(Vector A){ return atan2(A.y, A.x); } // polar angle of vector A
bool ToTheLeft(Point A, Point B, Point C){ return sgn((B - A) ^ (C - B)) > 0; } // test if vector(bc) is to the left of (ab)
bool ToTheLeft(Vector A, Vector B){ return sgn(A ^ B) > 0; } // test if vector B is to the left of vector A
double TriangleArea(Point A, Point B, Point C){ return ((B - A) ^ (C - A)) / 2; }

bool cmp1(const Point &A, const Point &B){
	return cmp(A.ang, B.ang) == 0 ? A * A < B * B : A.ang < B.ang;
}

const int N = 55;

int T, n;
Point p[N], t[N];
double dp[N][N], ans;

inline void solve(int O){
	int tid = 0;
	for(int j = 1; j <= n; j++){
		if(j == O)	continue;
		if(cmp(p[j].y, p[O].y) < 0)	continue;
		t[++tid] = p[j] - p[O];
		t[tid].ang = Angle(p[j] - p[O]);
	}
	sort(t+1, t+tid+1, cmp1);
	memset(dp, 0, sizeof dp);
	for(int i = 1; i <= tid; i++){
		for(int j = 1; j < i; j++){
			if(cmp(t[j].ang, t[i].ang) == 0)	continue;
			bool ok = true;
			for(int k = j + 1; k < i; k++){
				if(ToTheLeft(t[j], t[k]) && ToTheLeft(t[k], t[i]) && ToTheLeft(t[i] - t[j], t[k] - t[j])){
					ok = false;
					break;
				}
			}
			if(!ok)	continue;
			double ijO = fabs(TriangleArea(Point(0, 0), t[j], t[i]));
			dp[i][j] = max(dp[i][j], ijO);
			if(sgn(t[j] ^ t[j-1]) != 0)
				for(int k = 1; k < j; k++)
					if(ToTheLeft(t[j] - t[k], t[i] - t[k]))
						dp[i][j] = max(dp[i][j], ijO + dp[j][k]);
			ans = max(ans, dp[i][j]);
		}
	}
}

int main(){
	scanf("%d", &T);
	while(T--){
		scanf("%d", &n);
		ans = 0;
		for(int i = 1; i <= n; i++)	p[i].read();
		for(int i = 1; i <= n; i++)	solve(i);
		printf("%.1f\n", ans);
	}
	return 0;
}