题解 UVA1331 【Minimax Triangulation】

Log_x

2018-04-15 15:29:21

Solution

## Solution - 先把点统一处理成逆时针顺序(若用叉积算多边形面积为负数则为顺时针)。 - 设 $f[l][r]$ 表示从多边形上第 $l$ 个点 $A_l$ 到第 $r$ 个点 $A_r$ 之间的区域全部分割成三角形后,最大三角形面积的最小值。 - 注意因为多边形首尾顺次相接,$l$ 可以大于 $r$。 - 记 $nxt[i] = i + 1(1 \le i < n), nxt[n] = 1$,则 DP 边界为 $f[i][nxt[i]] = 0$。 - 转移为:$f[l][r] = \min\{\max\{f[l][i],\ S_{\triangle A_lA_iA_r},\ f[i][r]\}\} (\vec{A_iA_r} \times \vec{A_iA_r} > 0)$ - 注意题目给出的多边形不一定是凸多边形,可能存在如下情况: - ![](https://cdn.luogu.com.cn/upload/pic/21675.png) - 此时 $\triangle A_l A_i A_r$ 是不合法的,但同时我们也会发现用叉积计算结果为负数,因此 DP 就只要判断 $\vec{A_iA_r} \times \vec{A_iA_r} > 0$。 - 最后答案为 $\min\{\max\{f[i][j],\ f[j][i]\}\} (i \neq j)$。 - 转移顺序不好处理,可用记忆化搜索实现。 ## Code ```cpp #include <iostream> #include <cstdio> #include <algorithm> using namespace std; const int Maxn = 0x3f3f3f3f; const int N = 55; int nxt[N], f[N][N], n, m, Ans; struct point { int x, y; point() {} point(int X, int Y): x(X), y(Y) {} friend inline point operator - (const point &a, const point &b) { return point(b.x - a.x, b.y - a.y); } friend inline int operator * (const point &a, const point &b) { return a.x * b.y - b.x * a.y; } }a[N]; inline int Max(int x, int y) {return x > y ? x : y;} inline int Min(int x, int y) {return x < y ? x : y;} inline void CkMin(int &x, int y) {if (x > y) x = y;} inline int dp(int l, int r) { if (f[l][r] != -1) return f[l][r]; if (r == nxt[l]) return f[l][r] = 0; int res = Maxn; for (int i = nxt[l]; i != r; i = nxt[i]) { int tmp = (a[i] - a[r]) * (a[i] - a[l]); if (tmp > 0) CkMin(res, Max(Max(dp(l, i), tmp), dp(i, r))); } return f[l][r] = res; } int main() { while (scanf("%d", &m) != EOF) { while (m--) { scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d%d", &a[i].x, &a[i].y); for (int i = 1; i < n; ++i) nxt[i] = i + 1; nxt[n] = 1; int sum = 0; for (int i = 1; i < n; ++i) sum += a[i] * a[i + 1]; sum += a[n] * a[1]; if (sum < 0) for (int i = 1, im = n >> 1; i <= im; ++i) swap(a[i], a[n - i + 1]); for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) f[i][j] = -1; for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) if (i != j) dp(i, j); Ans = Maxn; for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) if (i != j) CkMin(Ans, Max(f[i][j], f[j][i])); printf("%.1lf\n", (double)Ans / 2.0); } } return 0; } ```