解題區/解題區 - UVa

UVa 1336 - Fixing the Great Wall

Problem

有一台機器必須修復長城的所有位置，每一個位置的修復時間都是瞬間完成，但是移動必須耗時，而每一個位置的修復成本與修復時間呈現花費 c + d * t，求最少花費。

Sample Input

1
2
3
4
5
6
7
8
9
3 1 1000
1010 0 100
998 0 300
996 0 3
3 1 1000
1010 0 100
998 0 3
996 0 3
0 0 0

Sample Output

1
2
2084
1138

Solution

首先，可以藉由貪心得到，既然修復時間是瞬間，所經之處必然會修理完成。

因此狀態會呈現某一個區間已完成，並且停留在左端點或者是右端點，然而費用的計算則相當麻煩，因為計算某個區間而言，並不知道這區間花費的移動時間成本，只知道其最小花費。

反過來思考，利用潛熱的概念，預先支付往後所有未經過的位置所需要的花費，那麼就可以得到從左右端點彼此之間的移動時間 dt，將會增加未經過位置的所有 sumc，得到預支付花費 dt * sumc。

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
#include <stdio.h> 
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAXN 1024
#define INF 1000000005
struct Pos {
    int x, c, delta; // cost = c + t * delta
    bool operator<(const Pos &a) const {
        return x < a.x;
    }
} D[MAXN];
int sumD[MAXN];
double dp[MAXN][MAXN][2]; // [interval_length][l][stop interval left/right]
int main() {
    int N, X;
    double V;
    while (scanf("%d %lf %d", &N, &V, &X) == 3 && N) {
        for (int i = 1; i <= N; i++)
            scanf("%d %d %d", &D[i].x, &D[i].c, &D[i].delta);
        sort(D + 1, D + 1 + N);
        
        sumD[0] = 0;
        for (int i = 1; i <= N; i++)
            sumD[i] = sumD[i-1] + D[i].delta;
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= N + 1; j++) {
                dp[i][j][0] = dp[i][j][1] = INF;
            }
        }
        for (int i = 1; i <= N; i++) {
            double cost = sumD[N] * (fabs(X - D[i].x) / V) + D[i].c;
            dp[1][i][0] = dp[1][i][1] = cost;
        }
        
        for (int i = 2; i <= N; i++) {
            for (int j = 1; j + i - 1 <= N; j++) {
                int l = j, r = j + i - 1;
                double fromL, fromR;
                fromL = fromR = INF;
                fromL = dp[i-1][l+1][0] + (sumD[l] + sumD[N] - sumD[r]) * ((D[l+1].x - D[l].x) / V) + D[l].c;
                fromR = dp[i-1][l+1][1] + (sumD[l] + sumD[N] - sumD[r]) * ((D[r].x - D[l].x) / V) + D[l].c;
                dp[i][l][0] = min(fromL, fromR);
                
                fromL = dp[i-1][l][0] + (sumD[l-1] + sumD[N] - sumD[r-1]) * ((D[r].x - D[l].x) / V) + D[r].c;
                fromR = dp[i-1][l][1] + (sumD[l-1] + sumD[N] - sumD[r-1]) * ((D[r].x - D[r-1].x) / V) + D[r].c;
                dp[i][l][1] = min(fromL, fromR);
            }
        }
        printf("%d\n", (int) min(dp[N][1][0], dp[N][1][1]));
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 1356 - Bridge

Problem

給吊橋總長、塔與塔之間的纜線限制、塔的高度，纜線在塔與塔之間呈現拋物線，使用最少的塔，請問纜線離地面多高。

Sample Input

1
2
3
4
5
2
20 101 400 4042
1 2 3 4

Sample Output

1
2
3
4
5
Case 1:
1.00
Case 2:
1.60

Solution

可以藉由貪心得到塔的數量，但是拋物線的方程式並不明確，因此可以考慮二分的高度，來計算纜線夠不夠長。

得到拋物線方程式後，要計算拋物線長度，使用數值積分的方式得到。為了降低計算誤差，使用自適應辛普森積分法，也就是當預估方法的變異小到一定程度時，停止分段求值。

integral parabola length

$$\int{\sqrt{dx^{2} + dy^{2}}} = \int{\sqrt{1 + dy^{2}/dx^{2}} dx} \\ = \int{\sqrt{1 + f'(x)^{2}} dx}$$ 
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
#include <stdio.h> 
#include <math.h>
using namespace std;
class SimpsonIntegral {
public:
    const double eps = 1e-6;
    double a; // function coefficient
    double f(double x) { // usually replace
        return sqrt(1 + 4 * a * a * x * x);
    }
    void setCoefficient(double a) {
        this->a = a;
    } 
    double simpson(double a, double b, double fa, double fb, double fab) {
        return (fa + 4 * fab + fb) * (b - a) / 6.0;
    }
    double integral(double l, double r) {
        return integral(l, r, eps);
    }
private:
    double integral(double a, double b, double c, double eps, double A, double fa, double fb, double fc) {
        double ab = (a + b)/2, bc = (b + c)/2;
        double fab = f(ab), fbc = f(bc);
        double L = simpson(a, b, fa, fb, fab), R = simpson(b, c, fb, fc, fbc);
        if (fabs(L + R - A) <= 15 * eps)
            return L + R + (L + R - A) / 15.0;
        return integral(a, ab, b, eps/2, L, fa, fab, fb) + integral(b, bc, c, eps/2, R, fb, fbc, fc);
    }
    double integral(double a, double b, double eps) {
        double ab = (a + b) /2;
        double fa = f(a), fb = f(b), fab = f(ab);
        return integral(a, ab, b, eps, simpson(a, b, fa, fb, fab), fa, fab, fb);
    }
} tool;
// integral parabola length
// \int \sqrt_{dx^{2} + dy^{2}} = \int \sqrt_{1 + dy^{2}/dx^{2}} dx
// = \int \sqrt_{1 + f'(x)^{2}} dx
int main() {
    int testcase, cases = 0;
    double D, H, B, L;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%lf %lf %lf %lf", &D, &H, &B, &L);
        int n = ceil(B / D);
        double w = B / n, plen = L / n; // for a parabola
        double l = 0, r = H, len, mid;
        for (int it = 0; it < 100; it++) {
            mid = (l + r)/2; // parabola y = ax^2, pass (w/2, mid)
            tool.setCoefficient(4 * mid / w / w);
            len = 2 * tool.integral(0, w/2);
            if (len < plen)
                l = mid;
            else
                r = mid;
        }
        if (cases)	puts("");
        printf("Case %d:\n", ++cases);
        printf("%.2lf\n", H - l);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 1322 - Minimizing Maximizer

Problem

有一個 Sorter 可以排序區間 [l, r]，按照順序挑選 Sorter，使得可以在序列中找到最大值。

記住，請按照輸入順序使用，否則可以直接貪心掃描。

Sample Input

1
2
3
4
5
6
7
8
9
1
40 6
20 30
1 10
10 20
20 30
15 25
30 40

Sample Output

1
4

Solution

如果要求按照順序，則必然在前 i 個 Sorter，紀錄覆蓋 [1, r] 的最小值。

那麼當提供一個 Sorter 支持 [x, y]，則查找覆蓋 [1, r] 其中 r >= x 的條件下的最小值。看到符合前綴最小值的操作，套用 binary indexed tree 來進行極值查找。否則線性搜索很容易超時。

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
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <queue>
#include <functional>
#include <deque>
#include <assert.h>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define MAXN 65536
int BIT[MAXN];
void modify(int x, int val, int L) {
    while (x <= L) {
        BIT[x] = min(BIT[x], val);
        x += x&(-x);
    }
}
int query(int x) {
    int ret = INF;
    while (x) {
        ret = min(ret, BIT[x]);
        x -= x&(-x);
    }
    return ret;
}
int main() {
    int testcase, N, M, x, y;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &N, &M);
        vector< pair<int, int> > D;
        for (int i = 0; i <= N; i++)
            BIT[i] = INF;
        modify(N, 0, N); // [1, 1] => 0
        for (int i = 0; i < M; i++) {
            scanf("%d %d", &x, &y);
            int val = query(N - x + 1) + 1;
            modify(N - y + 1, val, N);
        }
        int ret = query(1);
        printf("%d\n", ret);
        if (testcase)
            puts("");
    }
    return 0;
}
/*
*/
Read More +
解題區/解題區 - UVa

UVa 1312 - Cricket Field

Problem

在網格中，找一個最大空白正方形。

Sample Input

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

Sample Output

1
4 3 4

Solution

其實就類似找最大空白矩形中的特例，取寬高最小的即可。

算法主要是排序所有平面上的點後，窮舉底部的一點，往垂直方向掃描收束。對兩個軸都要做一次。

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
#include <stdio.h>
#include <algorithm>
using namespace std;
// same 10043 - Chainsaw Massacre.
struct Pt {
    int x, y;
    Pt(int a = 0, int b = 0):
    x(a), y(b){}
    bool operator<(const Pt &p) const {
        if(p.x != x)
            return x < p.x;
        return y < p.y;
    }
};
bool cmp(Pt a, Pt b) {
    if(a.y != b.y)
        return a.y < b.y;
    return a.x < b.x;
}
Pt tree[3000];
int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while(testcase--) {
        int h, w, n;
        scanf("%d %d %d", &n, &h, &w);
        for (int i = 0; i < n; i++)
            scanf("%d %d", &tree[i].x, &tree[i].y);
        tree[n++] = Pt(0, 0);
        tree[n++] = Pt(h, w);
        tree[n++] = Pt(h, 0);
        tree[n++] = Pt(0, w);
        sort(tree, tree+n);
        int P = 0, Q = 0, L = 0;
        for (int i = 0; i < n; i++) {
            int mny = 0, mxy = w;
            for (int j = i+1; j < n; j++) {
                int l = min(tree[j].x-tree[i].x, mxy-mny);
                if (l > L)
                    P = tree[i].x, Q = mny, L = l;
                if(tree[j].x == tree[i].x)
                    continue;
                if(tree[j].y > tree[i].y)
                    mxy = min(mxy, tree[j].y);
                else
                    mny = max(mny, tree[j].y);
            }
        }
        sort(tree, tree+n, cmp);
        for (int i = 0; i < n; i++) {
            int mnx = 0, mxx = h;
            for (int j = i+1; j < n; j++) {
                int l = min(tree[j].y-tree[i].y, mxx-mnx);
                if (l > L)
                    P = mnx, Q = tree[i].y, L = l;
                if(tree[j].y == tree[i].y)
                    continue;
                if(tree[j].x > tree[i].x)
                    mxx = min(mxx, tree[j].x);
                else
                    mnx = max(mnx, tree[j].x);
            }
        }
        if (cases++)    puts("");
        printf("%d %d %d\n", P, Q, L);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 1153 - Keep the Customer Satisfied

Problem

每一個工作都有所需完成時間、截止日期。每一個時刻最多執行一項工作，請問最多能完成幾項工作。

Sample Input

1
2
3
4
5
6
7
8
9
1
6
7 15
8 20
6 8
4 9
3 21
5 22

Sample Output

1
4

Solution

類似 UVa 10154 - Weights and Measures 的做法。

按照截止日期由小排到大，接著嘗試放入每一個工作，當總需時間超過截止日期，把所需時間最多的工作給吐出來，這樣的貪心方法，將會使得工作數量最多。

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
#include <stdio.h>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <math.h>
#include <algorithm>
#include <assert.h>
using namespace std;
#define eps 1e-6
#define MAXN 1048576
// similar  UVa 10154 - Weights and Measures
pair<int, int> D[MAXN];
bool cmp(pair<int, int> a, pair<int, int> b) {
    if (a.second != b.second)
        return a.second < b.second;
    return a.first < b.first;
}
int main() {
    int testcase, N, x, y;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &N);
        for (int i = 0; i < N; i++) {
            scanf("%d %d", &x, &y);
            D[i] = make_pair(x, y);
        }
        sort(D, D+N, cmp);
        
        priority_queue<int> pQ; // max-heap
        int t = 0;
        for (int i = 0; i < N; i++) {
            pQ.push(D[i].first);
            t += D[i].first;
            if (t > D[i].second)
                t -= pQ.top(), pQ.pop();
        }
        printf("%d\n", (int) pQ.size());
        if (testcase)
            puts("");
    }
    return 0;
}
/*
 
 */
Read More +
解題區/解題區 - UVa

UVa 1151 - Buy or Build

Problem

建造網路需要一個最少花費將所有點連起，然而有一個特別的方案，使得某些點集相連會有一個特殊的花費，這些特別的方案總數 < 8。

其餘任兩點需要相連，則將會花費兩點距離的歐幾里德距離平方，求一個最少花費。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
1
7 3
2 4 1 2
3 3 3 6 7
3 9 2 4 5
0 2
4 0
2 0
4 2
1 3
0 5
4 4

Sample Output

1
17

Solution

看到 2D 平面，花費又是歐幾里得距離，可以利用 Delaunay 找到所有 EMST 的邊，邊的數量是線性 O(n) 的。

窮舉組合方案 O(2^8)，接著套用 MST 的算法來完成。

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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <assert.h>
#include <string.h>
#include <list>
using namespace std;
#define eps 1e-8
#define MAXN (1048576)
#define MAXV 1024
struct Point {
    double x, y;
    int id;
    Point(double a = 0, double b = 0, int c = -1):
    x(a), y(b), id(c) {}
    Point operator-(const Point &a) const {
        return Point(x - a.x, y - a.y);
    }
    Point operator+(const Point &a) const {
        return Point(x + a.x, y + a.y);
    }
    Point operator*(const double a) const {
        return Point(x * a, y * a);
    }
    Point operator/(const double a) const {
        return Point(x / a, y / a);
    }
    bool operator<(const Point &a) const {
        if (fabs(x - a.x) > eps) return x < a.x;
        if (fabs(y - a.y) > eps) return y < a.y;
        return false;
    }
    bool operator==(const Point &a) const {
        return fabs(x - a.x) < eps && fabs(y - a.y) < eps;
    }
    bool operator!=(const Point &a) const {
        return !(fabs(x - a.x) < eps && fabs(y - a.y) < eps);
    }
    void read(int id = -1) {
        this->id = id;
    }
    double dist(Point b) {
        return hypot(x - b.x, y - b.y);
    }
    double dist2(Point b) {
        return (x - b.x) * (x - b.x) + (y - b.y) * (y - b.y);
    }
    void print() {
        printf("point (%lf, %lf)\n", x, y);
    }
};
struct Point3D {
    double x, y, z;
    Point3D(double a = 0, double b = 0, double c = 0):
    x(a), y(b), z(c) {}
    Point3D(Point p) {
        x = p.x, y = p.y, z = p.x * p.x + p.y * p.y;
    }
    Point3D operator-(const Point3D &a) const {
        return Point3D(x - a.x, y - a.y, z - a.z);
    }
    double dot(Point3D a) {
        return x * a.x + y * a.y + z * a.z;
    }
};
struct Edge {
    int id;
    list<Edge>::iterator twin;
    Edge(int id = 0) {
        this->id = id;
    }
};
int cmpZero(double v) {
    if (fabs(v) > eps) return v > 0 ? 1 : -1;
    return 0;
}
double cross(Point o, Point a, Point b) {
    return (a.x-o.x)*(b.y-o.y) - (a.y-o.y)*(b.x-o.x);
}
Point3D cross(Point3D a, Point3D b) { // normal vector
    return Point3D(a.y * b.z - a.z * b.y
                   , -a.x * b.z + a.z * b.x
                   , a.x * b.y - a.y * b.x);
}
int inCircle(Point a, Point b, Point c, Point p) {
    if (cross(a, b, c) < 0)
        swap(b, c);
    Point3D a3(a), b3(b), c3(c), p3(p);
    // printf("%lf %lf %lf\n", a3.x, a3.y, a3.z);
    // printf("%lf %lf %lf\n", b3.x, b3.y, b3.z);
    // printf("%lf %lf %lf\n", c3.x, c3.y, c3.z);
    // printf("%lf %lf %lf\n", p3.x, p3.y, p3.z);
    b3 = b3 - a3, c3 = c3 - a3, p3 = p3 - a3;
    Point3D f = cross(b3, c3); // normal vector
    return cmpZero(p3.dot(f)); // check same direction, in: < 0, on: = 0, out: > 0
}
int intersection(Point a, Point b, Point c, Point d) { // seg(a, b) and seg(c, d)
    return cmpZero(cross(a, c, b)) * cmpZero(cross(a, b, d)) > 0
    && cmpZero(cross(c, a, d)) * cmpZero(cross(c, d, b)) > 0;
}
class Delaunay {
public:
    list<Edge> head[MAXV]; // graph
    Point p[MAXV];
    int n, rename[MAXV];
    void init(int n, Point p[]) {
        for (int i = 0; i < n; i++)
            head[i].clear();
        for (int i = 0; i < n; i++)
            this->p[i] = p[i];
        sort(this->p, this->p + n);
        for (int i = 0; i < n; i++)
            rename[p[i].id] = i;
        this->n = n;
        divide(0, n - 1);
    }
    void addEdge(int u, int v) {
        head[u].push_front(Edge(v));
        head[v].push_front(Edge(u));
        head[u].begin()->twin = head[v].begin();
        head[v].begin()->twin = head[u].begin();
    }
    void divide(int l, int r) {
        if (r - l <= 1) { // #point <= 2
            for (int i = l; i <= r; i++)
                for (int j = i+1; j <= r; j++)
                    addEdge(i, j);
            return;
        }
        int mid = (l + r) /2;
        divide(l, mid);
        divide(mid + 1, r);
        list<Edge>::iterator it;
        int nowl = l, nowr = r;
        // printf("divide %d %d\n", l, r);
        for (int update = 1; update; ) { // find left and right convex, lower common tangent
            update = 0;
            Point ptL = p[nowl], ptR = p[nowr];
            for (it = head[nowl].begin(); it != head[nowl].end(); it++) {
                Point t = p[it->id];
                double v = cross(ptR, ptL, t);
                if (cmpZero(v) > 0 || (cmpZero(v) == 0 && ptR.dist2(t) < ptR.dist2(ptL))) {
                    nowl = it->id, update = 1;
                    break;
                }
            }
            if (update) continue;
            for (it = head[nowr].begin(); it != head[nowr].end(); it++) {
                Point t = p[it->id];
                double v = cross(ptL, ptR, t);
                if (cmpZero(v) < 0 || (cmpZero(v) == 0 && ptL.dist2(t) < ptL.dist2(ptR))) {
                    nowr = it->id, update = 1;
                    break;
                }
            }
        }
        addEdge(nowl, nowr); // add tangent
        // printf("add base %d %d\n", nowl, nowr);
        for (int update = 1; true;) {
            update = 0;
            Point ptL = p[nowl], ptR = p[nowr];
            int ch = -1, side = 0;
            for (it = head[nowl].begin(); it != head[nowl].end(); it++) {
                // ptL.print(), ptR.print(), p[it->id].print();
                if (cmpZero(cross(ptL, ptR, p[it->id])) > 0
                    && (ch == -1 || inCircle(ptL, ptR, p[ch], p[it->id]) < 0))
                    ch = it->id, side = -1;
                // printf("test L %d %d %d\n", nowl, it->id, inCircle(ptL, ptR, p[ch], p[it->id]));
            }
            for (it = head[nowr].begin(); it != head[nowr].end(); it++) {
                if (cmpZero(cross(ptR, p[it->id], ptL)) > 0
                    && (ch == -1 || inCircle(ptL, ptR, p[ch], p[it->id]) < 0))
                    ch = it->id, side = 1;
                // printf("test R %d %d %d\n", nowr, it->id, inCircle(ptL, ptR, p[ch], p[it->id]));
            }
            if (ch == -1) break; // upper common tangent
            // printf("choose %d %d\n", ch, side);
            if (side == -1) {
                for (it = head[nowl].begin(); it != head[nowl].end(); ) {
                    if (intersection(ptL, p[it->id], ptR, p[ch])) {
                        head[it->id].erase(it->twin);
                        head[nowl].erase(it++);
                    } else
                        it++;
                }
                nowl = ch;
                addEdge(nowl, nowr);
            } else {
                for (it = head[nowr].begin(); it != head[nowr].end(); ) {
                    if (intersection(ptR, p[it->id], ptL, p[ch])) {
                        head[it->id].erase(it->twin);
                        head[nowr].erase(it++);
                    } else
                        it++;
                }
                nowr = ch;
                addEdge(nowl, nowr);
            }
        }
    }
    vector< pair<int, int> > getEdge() {
        vector< pair<int, int> > ret;
        list<Edge>::iterator it;
        for (int i = 0; i < n; i++) {
            for (it = head[i].begin(); it != head[i].end(); it++) {
                if (it->id < i)
                    continue;
                // printf("DG %d %d\n", i, it->id);
                ret.push_back(make_pair(p[i].id, p[it->id].id));
            }
        }
        return ret;
    }
} tool;
struct edge {
    int x, y;
    long long v;
    edge(int a = 0, int b = 0, long long c = 0):
    x(a), y(b), v(c) {}
    bool operator<(const edge &a) const {
        return v < a.v;
    }
};
int parent[1024], weight[1024];
void init(int n) {
    for(int i= 0; i <= n; i++)
        parent[i] = i, weight[i] = 1;
}
int findp(int x) {
    return x == parent[x] ? x : (parent[x]=findp(parent[x]));
}
int joint(int x, int y) {
    x = findp(x), y = findp(y);
    if (x == y) return 0;
    if(weight[x] > weight[y])
        weight[x] += weight[y], parent[y] = x;
    else
        weight[y] += weight[x], parent[x] = y;
    return 1;
}
int main() {
    int testcase, n, m, x, y;
    Point p[MAXV];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        int C[8], Ccost[8];
        vector<int> Cnode[8];
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &C[i], &Ccost[i]);
            for (int j = 0; j < C[i]; j++) {
                scanf("%d", &x);
                x--;
                Cnode[i].push_back(x);
            }
        }
        
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &x, &y);
            p[i] = Point(x, y, i);
        }
        tool.init(n, p);
        vector<edge> E;
        vector< pair<int, int> > DG = tool.getEdge();
        for (int i = 0; i < DG.size(); i++) {
            x = DG[i].first, y = DG[i].second;
            long long v = (p[x].x - p[y].x) * (p[x].x - p[y].x) +
            (p[x].y - p[y].y) * (p[x].y - p[y].y);
            E.push_back(edge(x, y, v));
        }
        sort(E.begin(), E.end());
        
        long long ret = 1LL<<60;
        for (int i = 0; i < (1<<m); i++) {
            init(n);
            long long cost = 0;
            for (int j = 0; j < m; j++) {
                if ((i>>j)&1) {
                    for (int k = 0; k < Cnode[j].size(); k++) {
                        joint(Cnode[j][0], Cnode[j][k]);
                    }
                    cost += Ccost[j];
                }
            }
            int e = 0;
            for (int j = 0; j < E.size(); j++) {
                x = E[j].x, y = E[j].y;
                if (joint(x, y)) {
                    cost += E[j].v;
                    e++;
                    if (e == n - 1)
                        break;
                }
            }
            ret = min(ret, cost);
        }
        printf("%lld\n", ret);
        if (testcase)
            puts("");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 805 - Polygon Intersections

Problem

給兩個簡單多邊形，求交集的每一個簡單多邊形。

並且輸出時把共線的點移除，順逆時針都可以。

Sample Input

1
2
3
4
3 2 1 0.5 3.5 8 5
5 1.5 3 2 7 6.5 6.5 6.5 3.25 4 4.5
0
0

Sample Output

1
2
3
4
Data Set 1
Number of intersection regions: 2
Region 1:(1.50,3.00)(1.59,3.72)(3.25,4.05)
Region 2:(4.43,4.29)(6.50,4.70)(6.50,4.00)(5.86,3.57)

Solution

求兩個簡單多邊形的交集，用 double connected edge list 來解決交集好像是可行的操作？但是重疊在一起好像就會炸掉。

因此直接定向搜索 (將多邊形都以順或逆時針表示，接著產生可行的簡單多邊形) 任何可行簡單多邊形的存在判定！需要判定簡單多邊形的邊上中點是否都在兩個簡單多邊形內部，套用射線法的算法。

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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <map>
#include <assert.h>
#include <vector>
#include <string.h>
using namespace std;
#define eps 1e-10
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}	
    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);
    }
    Pt operator*(const double a) const {
        return Pt(x * a, y * a);
    }
    bool operator==(const Pt &a) const {
    	return fabs(x - a.x) < eps && fabs(y - a.y) < eps;
    }
    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;
    }
    double length() {
        return hypot(x, y);
    }
    void read() {
        scanf("%lf %lf", &x, &y);
    }
};
const double pi = acos(-1);
int cmpZero(double v) {
    if (fabs(v) > eps) return v > 0 ? 1 : -1;
    return 0;
}
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
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);
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
struct Seg {
    Pt s, e;
    int label;
    Seg(Pt a = Pt(), Pt b = Pt(), int l=0): s(a), e(b), label(l) {
    }
    bool operator!=(const Seg &other) const {
        return !((s == other.s && e == other.e) || (e == other.s && s == other.e));
    }
};
int intersection(Pt as, Pt at, Pt bs, Pt bt) {
    if (cmpZero(cross(as, at, bs) * cross(as, at, bt)) <= 0 &&
        cmpZero(cross(bs, bt, as) * cross(bs, bt, at)) <= 0)
        return 1;
    return 0;
}
Pt getIntersect(Seg a, Seg b) {
    Pt u = a.s - b.s;
    double t = cross2(b.e - b.s, u)/cross2(a.e - a.s, b.e - b.s);
    return a.s + (a.e - a.s) * t;
}
double getAngle(Pt va, Pt vb) { // segment, not vector
    return acos(dot(va, vb) / va.length() / vb.length());
}
Pt rotateRadian(Pt a, double radian) {
    double x, y;
    x = a.x * cos(radian) - a.y * sin(radian);
    y = a.x * sin(radian) + a.y * cos(radian);
    return Pt(x, y);
}
int inPolygon(Pt p[], int n, Pt q) {
    int i, j, cnt = 0;
    for(i = 0, j = n-1; i < n; j = i++) {
        if(onSeg(p[i], p[j], q))
            return 1;
        if(p[i].y > q.y != p[j].y > q.y &&
        q.x < (p[j].x-p[i].x)*(q.y-p[i].y)/(p[j].y-p[i].y) + p[i].x)
        cnt++;
    }
    return cnt&1;
}
void formalOrder(vector<Pt> &A) { // to counter-clockwise
    int s = 0, n = (int) A.size();
    for (int i = 0; i < A.size(); i++)
        if (A[i] < A[s])
            s = i;
    if (cmpZero(cross(A[(s+n-1)%n], A[s], A[(s+1)%n])) < 0)
        reverse(A.begin(), A.end());
}
vector< pair<double, Pt> > getDividePolygon(vector<Pt> A, vector<Pt> B) {
    vector< pair<double, Pt> > ret;
    Pt p;
    double s = 0;
    for (int i = 0; i < A.size(); i++) {
        if (i)	s += (A[i] - A[i-1]).length();
        ret.push_back(make_pair(s, A[i]));
    }
    A.push_back(A[0]);
    for (int i = 0; i + 1 < A.size(); i++) {
        for (int j = 0, k = B.size() - 1; j < B.size(); k = j++) {
            if (intersection(B[j], B[k], A[i], A[i+1])) {
                if (cmpZero(cross(A[i], A[i+1], B[j])) || cmpZero(cross(A[i], A[i+1], B[k]))) {
                    p = getIntersect(Seg(B[j], B[k]), Seg(A[i], A[i+1]));
                    ret.push_back(make_pair(ret[i].first + (A[i] - p).length(), p));
                } else {
                    if (between(A[i], A[i+1], B[j])) {
                        p = B[j];
                        ret.push_back(make_pair(ret[i].first + (A[i] - p).length(), p));
                    }
                    if (between(A[i], A[i+1], B[k])) {
                        p = B[k];
                        ret.push_back(make_pair(ret[i].first + (A[i] - p).length(), p));
                    }
                }
            }
        } 
    }
    sort(ret.begin(), ret.end());
    int n = 1;
    for (int i = 1; i < ret.size(); i++) {
        if (cmpZero(ret[i].first - ret[n - 1].first))
            ret[n++] = ret[i];
    }
    ret.resize(n);
    return ret;
}
#define MAXM 131072
#define MAXN 512
int g[MAXN][MAXN], ban[MAXN], used[MAXN], fromAB[MAXN];
int nA, nB;
Pt D[MAXN], path[MAXN];
Pt arrA[MAXN], arrB[MAXN];
vector< vector<Pt> > ret;
void recordAns(Pt A[], int n) {
    int update;
    do {
        update = 0;
        for (int i = 0; i < n; i++) {
            if (onSeg(A[i], A[(i+2)%n], A[(i+1)%n])) {
                update = 1;
                int ridx = (i+1)%n;
                for (int j = ridx; j < n; j++)
                    A[j] = A[j+1];
                n--;
                break;
            }
        } 
    } while (update);
    if (n <= 2)	return ;
    vector<Pt> vA;
    vector<Pt> minExp;
    for (int i = 0; i < n; i++)
        vA.push_back(A[i]);
    formalOrder(vA);
    int st = 0;
    for (int i = 0; i < n; i++) {
        if (vA[i] < vA[st])
            st = i;
    }
    for (int i = st; i >= 0; i--)
        minExp.push_back(vA[i]);
    for (int i = n - 1; i > st; i--)
        minExp.push_back(vA[i]);
    for (int i = 0; i < ret.size(); i++) {
        if (ret[i].size() != minExp.size())
            continue;
        int same = 1;
        for (int j = 0; j < minExp.size(); j++)
            same &= minExp[j] == ret[i][j];
        if (same)
            return ;
    }
    ret.push_back(minExp);
}
void buildEdge(vector< pair<double, Pt> > pA, map<Pt, int> &Rlabel, int f)  {
    for (int i = 0, j = pA.size() - 1; i < pA.size(); j = i++) {
        int from = Rlabel[pA[j].second];
        int to = Rlabel[pA[i].second];
        g[from][to] |= f;
    }
}
void dfs(int u, int idx, int N, int st) {
    path[idx] = D[u], used[u] = 1;
    for (int i = 0; i < N; i++) {
        if (g[u][i] && i == st) {
            int ok = 1;
            for (int j = 0; j < N && ok; j++) {
                if (used[j] == 0)
                    ok &= !inPolygon(path, idx+1, D[j]);
            }
            for (int j = 0, k = idx; j <= idx; k = j++) {
                Pt mid = (path[j] + path[k]) * 0.5;
                ok &= inPolygon(arrA, nA, mid);
                ok &= inPolygon(arrB, nB, mid);
            }
            if (ok) {
                recordAns(path, idx+1);
            }
        }
        if (g[u][i] && !used[i] && !ban[i]) {
            dfs(i, idx+1, N, st);
        }
    }
    used[u] = 0;
}
bool cmp(vector<Pt> A, vector<Pt> B) {
    for (int i = 0; i < A.size() && i < B.size(); i++) {
        if (!(A[i] == B[i]))
            return A[i] < B[i];
    }
    return A.size() < B.size();
}
void solve(vector<Pt> A, vector<Pt> B) {
    ret.clear();
    
    for (int i = 0; i < A.size(); i++)
        arrA[i] = A[i];
    for (int i = 0; i < B.size(); i++)
        arrB[i] = B[i];
    nA = A.size();
    nB = B.size();
    formalOrder(A);
    formalOrder(B);
    
    vector< pair<double, Pt> > pA, pB;
    map<Pt, int> Rlabel;
    int label = 0;
    
    pA = getDividePolygon(A, B);
    pB = getDividePolygon(B, A);
    
    for (int i = 0; i < pA.size(); i++) {
        if (!Rlabel.count(pA[i].second)) {
            D[label] = pA[i].second, fromAB[label] = 1;
            Rlabel[pA[i].second] = label++;
        }
//		printf("%.2lf %.2lf\n", pA[i].second.x, pA[i].second.y);
    }
    for (int i = 0; i < pB.size(); i++) {
        if (!Rlabel.count(pB[i].second)) {
            D[label] = pB[i].second, fromAB[label] = 2;
            Rlabel[pB[i].second] = label++;
        }
    }
    
//	for (int i = 0; i < label; i++)
//		printf("%d : %lf %lf\n", i, D[i].x, D[i].y);
    int N = (int) Rlabel.size();
    memset(g, 0, sizeof(g));
    memset(ban, 0, sizeof(ban));
    buildEdge(pA, Rlabel, 1);
    buildEdge(pB, Rlabel, 2);
    for (int i = 0; i < N; i++) {
        int ok = inPolygon(arrA, A.size(), D[i]) && inPolygon(arrB, B.size(), D[i]);
        if (!ok)
            ban[i] = 1;
    }
    for (int i = 0; i < N; i++) {
        if (!ban[i]) {
            memset(used, 0, sizeof(used));
            dfs(i, 0, N, i);
        }
    }
    printf("Number of intersection regions: %d\n", ret.size());
    sort(ret.begin(), ret.end(), cmp);
    for (int i = 0; i < ret.size(); i++) {
        printf("Region %d:", i+1);
        for (int j = 0; j < ret[i].size(); j++)
            printf("(%.2lf,%.2lf)", ret[i][j].x, ret[i][j].y);
        puts("");
    }
}
int main() {
    int N, M, cases = 0;
    double x, y;
    while (scanf("%d", &N) == 1 && N) {
        vector<Pt> A, B;
        for (int i = 0; i < N; i++) {
            scanf("%lf %lf", &x, &y);
            A.push_back(Pt(x, y));
        }
        scanf("%d", &M);
        for (int i = 0; i < M; i++) {
            scanf("%lf %lf", &x, &y);
            B.push_back(Pt(x, y));
        }
        printf("Data Set %d\n", ++cases);
        for (int i = 0; i < A.size(); i++) {
            assert(!onSeg(A[i], A[(i+2)%A.size()], A[(i+1)%A.size()]));
        }
        for (int i = 0; i < B.size(); i++) {
            assert(!onSeg(B[i], B[(i+2)%B.size()], B[(i+1)%B.size()]));
        }
        solve(A, B);
    }
    return 0;
}
/*
9 -2 0 -3 1 -2 3 0 4 -2 2 -1 2 1 4 2 4 2 0
4 -3 2 3 2 3 0 -3 0
9 -2 0 -3 1 -2 3 0 4 -2 2 -1 2 1 4 2 4 2 0
4 -3 4 3 4 3 0 -3 0
9 -2 0 -3 1 -2 3 0 4 -2 2 -1 2 1 4 2 4 2 0
4 -3 3 3 3 3 2 -3 2
4 -2 2 -2 1 -1 1 -1 2
4 -1 3 0 2 0 3 -1 2
6 -3 2 -1 0 1 0 3 2 1 4 -1 4
6 -1 1 1 1 3 -1 1 -3 -1 -3 -3 -1
8 -2 3 -1 0 1 0 2 3 3 -1 1 -2 -1 -2 -3 -1
4 -2 3 -1 0 1 0 2 3
8 -3 2 -1 0 1 0 3 2 3 -1 1 -2 -1 -2 -3 -1
4 -3 2 -2 1 2 1 3 2
5 -3 -2 -3 2 0 0 3 2 3 -2
4 -2 1 2 1 2 -1 -2 -1
4 0 0 0 1 1 1 1 0
4 0 0 0 1 1 1 1 0
4 0 0 2 0 2 2 0 2
4 -1 3 2 3 2 -1 -1 -1
4 0 0 0 1 1 1 1 0
4 0 0 1 1 2 0 1 -1
4 0 0 1 0 1 1 0 1
4 0 0 0 1 -1 1 -1 0
3 2 1 8 5 0.5 3.5
5 1.5 3 2 7 6.5 6.5 6.5 3.25 4 4.5
10 -2 0 -2 3 0 2 1 3 1 1 2 3 3 0 1 -2 0 0 -1 -1
5 -3 1 4 2 -1 0 2 -1 -1 -2
4 0 0 1 0 1 1 0 1
4 -1 -1 2 -1 2 2 -1 2
0
0 
*/
Read More +
解題區/解題區 - UVa

UVa 804 - Petri Net Simulation

Problem

上網搜尋 Petri Net ，得到是一個輸入輸出端的操作，當輸入端都至少一個時，將會進行觸發，每一次觸發會將輸入端都少一個元素，而輸出端會多一個元素。

現在模擬轉換 n 次，每一次轉換只能觸發一條，保證最終停留的結果只有一種，而當轉換失敗時，則宣告死亡。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
1 0
2
-1 2 0
-2 1 0
100
3
3 0 0
3
-1 2 0
-2 -2 3 0
-3 1 0
100
3
1 0 0
3
-1 2 3 0
-2 1 0
-3 1 0
1
0

Sample Output

1
2
3
4
5
6
7
8
Case 1: still live after 100 transitions
Places with tokens: 1 (1)
Case 2: dead after 9 transitions
Places with tokens: 2 (1)
Case 3: still live after 1 transitions
Places with tokens: 2 (1) 3 (1)

Solution

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
#include <stdio.h>
#include <map>
#include <queue>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 1024
#define MAXM 1024
int N, P[MAXN], M, K;
vector<int> INPUT[MAXM], OUTPUT[MAXM];
void remove(int tid) {
    for (int i = 0; i < INPUT[tid].size(); i++) {
        P[INPUT[tid][i]]--;
    }
}
void resume(int tid) {
    for (int i = 0; i < INPUT[tid].size(); i++) {
        P[INPUT[tid][i]]++;
    }
}
int trigger(int tid) {
    int ok = 1;
    remove(tid);
    for (int i = 0; i < INPUT[tid].size(); i++)
        ok &= P[INPUT[tid][i]] >= 0;
    resume(tid);
    return ok;
}
void action(int tid) {
    remove(tid);
    for (int i = 0; i < OUTPUT[tid].size(); i++)
        P[OUTPUT[tid][i]]++;
}
void simulate() {
    for (int i = 0; i < K; i++) {
        int update = 0;
        for (int j = 0; j < M; j++) {
            if (trigger(j)) {
                update = 1;
                action(j);
                break;
            }
        }
        if (!update) {
            printf("dead after %d transitions\n", i);
            return;
        }
    }
    printf("still live after %d transitions\n", K);
}
int main() {
    int cases = 0;
    while (scanf("%d", &N) == 1 && N) {
        for (int i = 1; i <= N; i++)
            scanf("%d", &P[i]);
        scanf("%d", &M);
        for (int i = 0; i < M; i++) {
            int x;
            INPUT[i].clear(), OUTPUT[i].clear();
            while (scanf("%d", &x) == 1 && x) {
                if (x < 0)
                    INPUT[i].push_back(-x);
                if (x > 0)
                    OUTPUT[i].push_back(x);
            }
        }
        scanf("%d", &K);
        printf("Case %d: ", ++cases);
        simulate();
        printf("Places with tokens:");
        for (int i = 1; i <= N; i++) {
            if (P[i])
                printf(" %d (%d)", i, P[i]);
        }
        puts("\n");
    }
    return 0;
}
/*
 2
 1 0
 2
 -1 2 0
 -2 1 0
 100
 3
 3 0 0
 3
 -1 2 0
 -2 -2 3 0
 -3 1 0
 100
 3
 1 0 0
 3
 -1 2 3 0
 -2 1 0
 -3 1 0
 1
 0
 */
Read More +
解題區/解題區 - UVa

UVa 754 - Treasure Hunt

Problem

埃及金字塔考古開挖，寶藏在其中一個密室，現在給金字塔的所有密室圖，求最少要爆破幾個牆壁才能從最外面進入寶藏所在的密室。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
1
7
20 0 37 100
40 0 76 100
85 0 0 75
100 90 0 90
0 71 100 61
0 14 100 38
100 47 47 100
54.5 55.4

Sample Output

1
Number of doors = 2

Solution

網路上有人使用半平面交，不斷地從寶藏所在之處的凸包，每次拿凸包邊的中點，外偏一點再找半平面交，直到碰到外界。但外偏多少才能保證會在另一個密室？這外偏的想法當然不錯，但想到誤差可能，還是先挑戰別的想法。精神還是繞著 Bfs 走。

把之前的 Point Location 拿出來用，先用 Partition Slab Map 頂替，用 Trapezoidal Map 可能就 … 寫個半條命。得到可以支持 Point Location 的資料結構後，把 Dual graph 建造出來，就可以 Bfs 收工。

Partition Slab Map

Dual graph

夢月 (dreamoon) 提供更簡單實作的想法

n 只有 30，而且他的平面圗是很多直線構成的，對於每個區塊，我們可以快速得知他是在每條線的正方向或負方向，所以每個區塊都可以用長度至多 30 的元素只含 0,1 的 vector 表示，每跨越一個邊就是 vector 上某個 0 變成 1。用這樣的概念的話可以很好想很好寫
不過我所謂的很好想好好寫 …應該是在同時都曾經寫過我這方法和你那方法再來比較的話我是覺得這個方法比較好寫 …第一次寫的話或許還是要思考許久
實做的話可以對於每條直線，求出所有其他直線與他的交點，sort這些交點後，枚舉相鄰兩個交點的中點，求出該點對於其他所有直線是落在正區域或負區域，於是我們就知道只有該直線正負區域不同的兩個 vector 是相鄰的，於是就把所有邊建出來可以 bfs 了

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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <vector>
using namespace std;
#define eps 1e-8
#define MAXM 32767
struct Pt {
    double x, y;
    int label;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}	
    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);
    }
    Pt operator*(const double a) const {
        return Pt(x * a, y * a);
    }
    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;
    }
    bool operator==(const Pt &a) const {
        return fabs(x - a.x) < eps && fabs(y - a.y) < eps;
    }
};
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
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);
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
struct Seg {
    Pt s, e;
    double angle;
    int label;
    Seg(Pt a = Pt(), Pt b = Pt()):s(a), e(b) {
        angle = atan2(e.y - s.y, e.x - s.x);
    }
    bool operator<(const Seg &other) const {
        if (fabs(angle - other.angle) > eps)
            return angle > other.angle;
        if (cross(other.s, other.e, s) > -eps)
            return true;
        return false;
    }
    double interpolate(double x) const {
        Pt p1 = s, p2 = e;
        if (p1.x == p2.x) return p1.y;
        return p1.y + (double)(p2.y - p1.y) / (p2.x - p1.x) * (x - p1.x);
    }
};
int cmpZero(double v) {
    if (fabs(v) > eps) return v > 0 ? 1 : -1;
    return 0;
}
Pt getIntersect(Seg a, Seg b) {
    Pt u = a.s - b.s;
    double t = cross2(b.e - b.s, u)/cross2(a.e - a.s, b.e - b.s);
    return a.s + (a.e - a.s) * t;
}
int intersection(Pt a, Pt b, Pt c, Pt d) { // seg(a, b) and seg(c, d)
    return cmpZero(cross(a, c, b)) * cmpZero(cross(a, b, d)) > 0
        && cmpZero(cross(c, a, d)) * cmpZero(cross(c, d, b)) > 0;
}
#define MAXH 100.0f
#define MAXW 100.0f
int validPos(double x, double y) {
    return 0 <= x && x <= MAXH
        && 0 <= y && y <= MAXW;	
}
struct CMP {
    static double x;
    double interpolate(const Pt& p1, const Pt& p2, double& x) {
        if (p1.x == p2.x) return p1.y;
        return p1.y + (double)(p2.y - p1.y) / (p2.x - p1.x) * (x - p1.x);
    }
    bool operator()(const Seg &i, const Seg &j) {
        double v1 = interpolate(i.s, i.e, x), v2 = interpolate(j.s, j.e, x);
        if (fabs(v1 - v2) > eps)
            return v1 < v2;
        return false;
    }
};
double CMP::x = 0;
class DisjointSet {
    public:
    int parent[MAXM];
    int findp(int x) {
        return parent[x] == x ? x : parent[x] = findp(parent[x]);
    }
    int joint(int x, int y) {
        x = findp(x), y = findp(y);
        if (x == y)	return 0;
        parent[x] = y;
        return 1;
    }
    void init(int n) {
        for (int i = 0; i <= n; i++)
            parent[i] = i;
    }
};
class PartitionMap {
    public:
    int n;
    DisjointSet disjointSet;
    Seg segs[1024];
    vector<double> X;
    vector<int> g[MAXM];
    set<Seg, CMP> tree[MAXM];
    vector<Pt> dual[MAXM];
    vector<Seg> dualLBound[MAXM], dualUBound[MAXM];
    vector<Pt> pts;
    void partition() {
        X.clear();
        for (int i = 0; i < n; i++) {
            X.push_back(segs[i].s.x);
            X.push_back(segs[i].e.x);
            for (int j = i+1; j < n; j++) {
                if (intersection(segs[i].s, segs[i].e, segs[j].s, segs[j].e)) {
                    Pt p = getIntersect(segs[i], segs[j]);
                    if (validPos(p.x, p.y)) {
                        X.push_back(p.x);
                    }
                }
            }
        }
        
        sort(X.begin(), X.end());
        int m = 1;
        for (int i = 1; i < X.size(); i++) {
            if (fabs(X[i] - X[m - 1]) > eps)
                X[m++] = X[i];
        }		
        X.resize(m);
        for (int i = 0; i < m; i++)
            tree[i].clear();
    }
    void buildMap() {
        int m = X.size();
        int region = 0;
        for (int i = 0; i < m; i++) {
            dual[i].clear();
            dualLBound[i].clear();
            dualUBound[i].clear();
        }
        pts.clear();
        for (int i = 0; i < m - 1; i++) {
            double mid = (X[i] + X[i+1])/2;
            CMP::x = mid;
            for (int j = 0; j < n; j++) {
                double sx = segs[j].s.x, ex = segs[j].e.x;
                if (sx <= X[i] && X[i+1] <= ex) {
                    tree[i].insert(segs[j]);
                }
            }
            set<Seg, CMP>::iterator it = tree[i].begin(), jt = it;
            jt++;
            for (; it != tree[i].end() && jt != tree[i].end(); it++, jt++) {
                double a = (*it).interpolate(mid);
                double b = (*jt).interpolate(mid);
                double c = (a + b) /2.0;
                Pt p(mid, c);
                p.label = region++;
                dual[i].push_back(p);
                dualLBound[i].push_back(*it);
                dualUBound[i].push_back(*jt);
                pts.push_back(p);
            }
        }
//		printf("region %d\n", region);
            
        disjointSet.init(region);
        
        vector<int> tmpg[MAXM];
        for (int i = 0; i < m; i++) {
            for (int j = 1; j < dual[i].size(); j++) {
                int x = dual[i][j].label;
                int y = dual[i][j-1].label;
                tmpg[x].push_back(y);
                tmpg[y].push_back(x);
            }
        }
        for (int i = 0; i < m - 2; i++) {
            for (int j = 0; j < dual[i].size(); j++) {
                for (int k = 0; k < dual[i+1].size(); k++) {
                    double y1, y2, y3, y4;
                    
                    y1 = dualLBound[i][j].interpolate(X[i+1]);
                    y2 = dualUBound[i][j].interpolate(X[i+1]);
                    y3 = dualLBound[i+1][k].interpolate(X[i+1]);
                    y4 = dualUBound[i+1][k].interpolate(X[i+1]);
                    if (max(y1, y3) < min(y2, y4)) {					
//						printf("%lf %lf, %lf %lf\n", y1, y2, y3, y4);
//						getchar();
                        Pt p(X[i+1], (max(y1, y3) + min(y2, y4))/2);
                        int ok = 1;
                        for (int t = 0; t < n && ok; t++) {
                            if (onSeg(segs[t].s, segs[t].e, p))
                                ok = 0;
                        }
                        if (ok)
                            disjointSet.joint(dual[i][j].label, dual[i+1][k].label);
                        else {
                            tmpg[dual[i][j].label].push_back(dual[i+1][k].label);
                            tmpg[dual[i+1][k].label].push_back(dual[i][j].label);
                        }
                    }
                }
            }
        }
        
        for (int i = 0; i < region; i++)
            g[i].clear();
        for (int i = 0; i < region; i++) {
            int x = disjointSet.findp(i);
            for (int j = 0; j < tmpg[i].size(); j++) {
                int y = disjointSet.findp(tmpg[i][j]);
                g[x].push_back(y);
            }
        }
        
        int diff = 0;
        for (int i = 0; i < region; i++) {
            sort(g[i].begin(), g[i].end());
            g[i].resize(unique(g[i].begin(), g[i].end()) - g[i].begin());
            if (g[i].size())
                diff++;
        }
//		printf("diffffffff %d\n", diff);
    }
    
    int findLocation(Pt p) {
        set<Seg>::iterator it, jt;
        for (int i = 0; i < X.size() - 1; i++) {
            if (X[i] <= p.x && p.x <= X[i+1]) {
                double mid = (X[i] + X[i+1])/2;
                CMP::x = mid;
                it = tree[i].lower_bound(Seg(p, p));
                jt = it, jt--;
                double a = (*it).interpolate(mid);
                double b = (*jt).interpolate(mid);
                double c = (a + b) /2.0;
                for (int j = 0; j < dual[i].size(); j++) {
                    if (dual[i][j] == Pt(mid, c))
                        return disjointSet.findp(dual[i][j].label);
                }
            }
        }
        return -1;
    }
    int path(Pt p, Pt q) {
        int st = findLocation(p);
        int ed = findLocation(q);
        map<int, int> dist;
        queue<int> Q;
        Q.push(st), dist[st] = 0;
//		printf("st %d ed %d\n", st, ed);
        while (!Q.empty()) {
            int u = Q.front(), d = dist[u] + 1;
            Q.pop();
//			printf("%d %lf %lf, dist %d\n", u, pts[u].x, pts[u].y, d);
            if (u == ed)	return d - 1;
            for (int i = 0; i < g[u].size(); i++) {
                int v = g[u][i];
                if (dist.count(v))	continue;
                dist[v] = d, Q.push(v);
//				printf("%d -> %d\n", u, v);
            }
        }
        return -1;
    }
    
    void init(Seg A[], int n) {
        for (int i = 0; i < n; i++)
            this->segs[i] = A[i];
        this->n = n;
        
        for (int i = 0; i < n; i++) {
            if (segs[i].e < segs[i].s)
                swap(segs[i].s, segs[i].e);
        }
        
        partition();
        buildMap();		
    }
} mMap;
int main() {
    int testcase, n;
    double sx, sy, ex, ey;
    Seg segs[128];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        
        for (int i = 0; i < n; i++) {
            scanf("%lf %lf %lf %lf", &sx, &sy, &ex, &ey);
            segs[i] = Seg(Pt(sx, sy), Pt(ex, ey));
        }
        
        // inter map
        segs[n] = Seg(Pt(0, 0), Pt(MAXH, 0)), n++;
        segs[n] = Seg(Pt(MAXH, 0), Pt(MAXH, MAXW)), n++;
        segs[n] = Seg(Pt(MAXH, MAXW), Pt(0, MAXW)), n++;
        segs[n] = Seg(Pt(0, MAXW), Pt(0, 0)), n++;
        
        // outer map
        int GAP = 10;
        segs[n] = Seg(Pt(-GAP, -GAP), Pt(MAXH + GAP, -GAP)), n++;
        segs[n] = Seg(Pt(MAXH + GAP, -GAP), Pt(MAXH + GAP, MAXW + GAP)), n++;
        segs[n] = Seg(Pt(MAXH + GAP, MAXW + GAP), Pt(-GAP, MAXW + GAP)), n++;
        segs[n] = Seg(Pt(-GAP, MAXW + GAP), Pt(-GAP, -GAP)), n++;
        
        mMap.init(segs, n);
        
        scanf("%lf %lf", &sx, &sy);
        int ret = mMap.path(Pt(sx, sy), Pt(-GAP/2, -GAP/2));
        printf("Number of doors = %d\n", ret);
        if (testcase)
            puts("");
    }
    return 0;
}
/*
2
7
20 0 37 100
40 0 76 100
85 0 0 75
100 90 0 90
0 71 100 61
0 14 100 38
100 47 47 100
54.5 55.4
7
20 0 37 100
40 0 76 100
85 0 0 75
100 90 0 90
0 71 100 61
0 14 100 38
100 47 47 100
1 1
*/
Read More +
解題區/解題區 - UVa

UVa 751 - Triangle War

Problem

兩名玩家進行放邊的操作，當其中一名玩家成功創建一個三角形，則可以再放入一邊，直到該操作無法創建一個新的三角形，則進行輪替。最大化自己與對方的分數差異。

一開始先模擬兩名玩家的操作過程。

Sample Input

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
4
6
2 4
4 5
5 9
3 6
2 5
3 5
7
2 4
4 5
5 9
3 6
2 5
3 5
7 8
6
1 2
2 3
1 3
2 4
2 5
4 5
10
1 2
2 5
3 6
5 8
4 7
6 10
2 4
4 5
4 8
7 8

Sample Output

1
2
3
4
Game 1: B wins.
Game 2: A wins.
Game 3: A wins.
Game 4: B wins.

Solution

這題很妙，總之先定義狀態 dp(盤面狀況，剩餘三角形) = 最大化差異。

那麼轉移方程要看操作是否造成輪替，如果仍然為自己，則把下一步的最大化結果累加上來，反之扣除。

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
#include <stdio.h>
#include <string.h>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
int dp[1<<18][11];
char used[1<<18][11] = {};
int trans[11][11], tri[10];
int countTri(int state) {
    int ret = 0;
    for (int i = 0; i < 9; i++) {
        if ((state&tri[i]) == tri[i])
            ret++;
    }
    return ret;
}
int dfs(int state, int score) {
    if (used[state][score])		return dp[state][score];
    used[state][score] = 1;
    
    int ret = 0, nstate, had = 9 - score, c, t;
    for (int i = 0; i < 18; i++) {
        if ((state>>i)&1) {
            nstate = state ^ (1<<i); // used it.
            c = countTri(((1<<18)-1)^nstate);
            if (c > had) { // create new
                t = c - had + dfs(nstate, score - (c - had));
                ret = max(ret, t);
            } else {
                t = score - dfs(nstate, score);
                ret = max(ret, t);
            }
        }
    }
    dp[state][score] = ret;
    return ret;
}
int main() {	
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    trans[1][2] = 0, trans[1][3] = 1;
    trans[2][3] = 2;
    trans[2][4] = 3, trans[2][5] = 4, trans[3][5] = 5, trans[3][6] = 6;
    trans[4][5] = 7, trans[5][6] = 8;
    trans[4][7] = 9, trans[4][8] = 10, trans[5][8] = 11, trans[5][9] = 12, trans[6][9] = 13, trans[6][10] = 14;
    trans[7][8] = 15, trans[8][9] = 16, trans[9][10] = 17;
    tri[0] = (1<<0)|(1<<1)|(1<<2);
    tri[1] = (1<<3)|(1<<4)|(1<<7);
    tri[2] = (1<<2)|(1<<4)|(1<<5);
    tri[3] = (1<<5)|(1<<6)|(1<<8);
    tri[4] = (1<<9)|(1<<10)|(1<<15);
    tri[5] = (1<<7)|(1<<10)|(1<<11);
    tri[6] = (1<<11)|(1<<12)|(1<<16);
    tri[7] = (1<<8)|(1<<12)|(1<<13);
    tri[8] = (1<<13)|(1<<14)|(1<<17);
    int testcase, cases = 0;
    int n, x, y;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        
        int state = 0, A = 0, B = 0, turn = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &x, &y);
            if (x > y)	swap(x, y);
            int c = countTri(state|(1<<trans[x][y])) - countTri(state);
            if (c) {
                if (turn == 0)		A += c;
                else				B += c;
            } else {
                turn = !turn;
            }
            state |= 1<<trans[x][y];
        }
//		printf("score %d %d\n", A, B);
        state = ((1<<18)-1)^state; // unused: 1
        int had = A + B;
        int mx = dfs(state, 9 - had);
        if (turn == 0)	A += mx, B += 9 - had - mx;
        else			B += mx, A += 9 - had - mx;
        printf("Game %d: %s wins.\n", ++cases, A > B ? "A" : "B");
    }
    return 0;
}
/*
4
6
2 4
4 5
5 9
3 6
2 5
3 5
7
2 4
4 5
5 9
3 6
2 5
3 5
7 8
6
1 2
2 3
1 3
2 4
2 5
4 5
10
1 2
2 5
3 6
5 8
4 7
6 10
2 4
4 5
4 8
7 8
*/
Read More +