https://vjudge.net/contest/436638
C - Empty Convex Polygons
题意：最大空凸包模板题。
参考 https://blog.csdn.net/cdsszjj/article/details/79366813
dp
先把所有点按照极角从小到大排序，设 O 是最大空凸包上最下最左的点，dp[i][j] 表示 Oij 是凸包上最后一个三角形。
枚举 O，枚举 i,j,k，则有 dp[i][j]=kmax(dp[j][k]+SΔOij)，其中 Oijk 是凸的。那么如果能够维护一个序列，使得对于已知的 O,i,j，序列上任意点 k 都满足 Oijk 是凸的且围成的凸包中不含其它点，就可以通过在计算dp的同时记录dp的最大值，而不需要枚举 k，这样复杂度就降为 O(n3) 了。
枚举 O,i，先取 j=i−1，如果 O,i,j 不共线，则取这个 j，否则 j 减小直到 O,i,j 不共线。确定了 O,i,j 后，找到第一个凸的 k，更新答案，并将下一个 j 取为 k。
要注意只有当 O,i,i−1 不共线时才记录dp值，否则只更新答案而不更新dp数组，这是因为若 O,i,i−1 共线，则之后再用到 dp[i][i−1] 时，构成的凸包内会包含 i−1 这个点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| #include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
const double eps = 1e-8;
const double PI = acos(-1);
int T;
int n, m;
double ans, dp[60][60];
struct Point {
int x, y;
Point(int x = 0, int y = 0) :x(x), y(y) {}
int dis() { return x * x + y * y; }
}a[N], b[N], O;
typedef Point Vector;
Vector operator+(Vector A, Vector B) { return Vector(A.x + B.x, A.y + B.y); }
Vector operator-(Point A, Point B) { return Vector(A.x - B.x, A.y - B.y); }
bool operator<(const Point& a, const Point& b) {
return a.x < b.x || (a.x == b.x&&a.y < b.y);
}
int Cross(Vector A, Vector B) { return A.x*B.y - A.y*B.x; }
double Area(Point A, Point B, Point C) { return fabs(Cross(B - A, C - A) * 0.5); }
bool cmp(Point A, Point B) {
int a = Cross(A - O, B - O);
if (a != 0)return a > 0;
else return (A - O).dis() < (B - O).dis();
}
void solve() {
memset(dp, 0, sizeof(dp));
sort(b + 1, b + m + 1, cmp);
for (int i = 1; i <= m; i++) {
int j = i - 1;
while (j && Cross(b[i] - O, b[j] - O) == 0)j--;
int flg = (j == i - 1);
while (j) {
int k = j - 1;
while (k && Cross(b[i] - b[k], b[j] - b[k]) > 0)k--;
double tmp = Area(O, b[i], b[j]);
if (k)tmp += dp[j][k];
ans = max(ans, tmp);
if (flg)dp[i][j] = tmp;
j = k;
}
if (flg)for (int j = 2; j < i; j++)dp[i][j] = max(dp[i][j], dp[i][j - 1]);
}
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (int i = 1; i <= n; i++)scanf("%d%d", &a[i].x, &a[i].y);
ans = 0;
for (int i = 1; i <= n; i++) {
m = 0;
O = a[i];
for (int j = 1; j <= n; j++) {
if (a[j].y > a[i].y || (a[j].y == a[i].y&&a[j].x > a[i].x))b[++m] = a[j];
}
solve();
}
printf("%.1f\n", ans);
}
return 0;
}
|
