解題區/解題區 - UVa

UVa 1331 - Minimax Triangulation

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

將一個簡單多邊形三角化，並且讓最大面積的三角形越小越好。

Sample Input

1
2
3
4
5
6
7
8
1
6
7 0
6 2
9 5
3 5
0 3
1 1

Sample Output

1
9.0

Solution

矩陣鏈乘積的方式著手 dp。

在此必須檢查劃分兩區間的三角形中內部不包含任何點，這裡利用外積 cross 進行計算。

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
#define eps 1e-6
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    x(a), y(b) {}
    bool operator<(const Pt &a) const {
        if (fabs(x-a.x) > eps)
            return x < a.x;
        if (fabs(y-a.y) > eps)
            return y < a.y;
        return false;
    }
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    bool operator==(const Pt &a) const {
    	return (fabs(x - a.x) < eps && fabs(y - a.y) < eps);
    }
    void read() {
        scanf("%lf %lf", &x, &y);
    }
};
struct Seg {
    Pt s, e;
    Seg(Pt a = Pt(), Pt b = Pt()):
        s(a), e(b) {}
};
double dist(Pt a, Pt b) {
    return hypot(a.x - b.x, a.y - b.y);
}
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= 0 && dot(c - b, a - b) >= 0;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
int intersection(Pt as, Pt at, Pt bs, Pt bt) {
    if(cross(as, at, bs) * cross(as, at, bt) < 0 &&
       cross(at, as, bs) * cross(at, as, bt) < 0 &&
       cross(bs, bt, as) * cross(bs, bt, at) < 0 &&
       cross(bt, bs, as) * cross(bt, bs, at) < 0)
        return 1;
    return 0;
}
double distProjection(Pt as, Pt at, Pt s) {
    int a, b, c;
    a = at.y - as.y;
    b = as.x - at.x;
    c = - (a * as.x + b * as.y);
    return fabs(a * s.x + b * s.y + c) / hypot(a, b);
}
double ptToSeg(Seg seg, Pt p) {
    double c = 1e+30;
    if(between(seg.s, seg.e, p))
        c = min(c, distProjection(seg.s, seg.e, p));
    else
        c = min(c, min(dist(seg.s, p), dist(seg.e, p)));
    return c;
}
double getArea(Pt a, Pt b, Pt c) {
    return fabs(cross(a, b, c))/2.0;
}
int isEmptyTriangle(Pt a, Pt b, Pt c, Pt D[], int n) {
    for (int i = 0; i < n; i++) {
        if (D[i] == a || D[i] == b || D[i] == c)
            continue;
        if (cross(a, D[i], b) * cross(a, D[i], c) < 0 && 
            cross(b, D[i], a) * cross(b, D[i], c) < 0 &&
            cross(c, D[i], a) * cross(c, D[i], b) < 0)
            return 0;
    }
    return 1;
}
int main() {
    int testcase, n;
    Pt D[128];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            D[i].read();
        for (int i = 0; i < n; i++)
            D[i + n] = D[i];
        double dp[128][128];
        for (int i = 0; i < 2 * n; i++) {
            for (int j = 0; j < 2 * n; j++) {
                dp[i][j] = 1e+30;
            }
            dp[i][i] = dp[i][i+1] = 0;
        }
        double ret = 1e+30;
        for (int i = 2; i < n; i++) {
            for (int j = 0; j < n; j++) {// [j, j+i]
                int l = j, r = j + i;
                double &v = dp[l][r];
                for (int k = l+1; k < r; k++) {
                    if (isEmptyTriangle(D[l], D[r], D[k], D, n))
                        v = min(v, max(max(dp[l][k], dp[k][r]), getArea(D[l], D[r], D[k])));
                }
            }
        }
        for (int i = 0; i < n; i++)
            ret = min(ret, dp[i][i + n - 1]);
        printf("%.1lf\n", ret);
    }
    return 0;
}
/*
1
6
7 0
6 2
9 5
3 5
0 3
1 1
*/