解題區►解題區 - 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 <= 2) { // #point <= 3
            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 +
解題區►解題區 - UVa

UVa 509 - RAID

Problem

參照《算法競賽入門經典》一書

一種磁碟儲存的機制，磁碟除了資料儲存，同時也會賦予檢查碼，來修正錯誤的資訊，即便能力相當有限，最多修正一個錯誤位元。

現在要求的工作是進行錯誤位元的復原，並且輸出 16 進制下的資料，如果資料不足 4 bits，則剩餘位元接補上 0。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
5 2 5
E
0001011111
0110111011
1011011111
1110101100
0010010111
3 2 5
E
0001111111
0111111011
xx11011111
3 5 1
O
11111
11xxx
x1111
0

Sample Output

1
2
3
Disk set 1 is valid, contents are: 6C7A79EDFC
Disk set 2 is invalid.
Disk set 3 is valid, contents are: FFC

Solution

這題很簡單，但是一直沒注意到陣列開太小而炸掉，我的預設記憶體不夠大而 WA。剩下的細節則注意錯誤位元如果是檢查碼就可以無視，而同時檢查碼只支持修正一個位元，如果需要修正兩個以上則表示無法復原。

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <iostream>
#include <sstream>
using namespace std;
char mem[128][65536];
int main() {
    int cases = 0;
    int D, S, B;
    char kind[8];
    while (scanf("%d %d %d", &D, &S, &B) == 3 && D) {
        scanf("%s", kind);
        for (int i = 0; i < D; i++)
            scanf("%s", mem[i]);
        int n = S * B, kv = kind[0] == 'E' ? 0 : 1;
        int err = 0;
        for (int i = 0, j = 0; i < n; i += S, j++) {
            j %= D;
            for (int p = i; p < i + S; p++) {
                int broken = 0, brokenPos = 0, XOR = 0;
                for (int k = 0; k < D; k++) {
                    if (mem[k][p] == 'x')
                        broken++, brokenPos = k;
                    else
                        XOR ^= mem[k][p] - '0';
                }
                if (broken >= 2)
                    err = 1;
                else if (broken == 1) {
                    if (brokenPos == j) {
                    } else {
                        mem[brokenPos][p] = '0' + (kv^XOR);
                    }
                } else {
                    if (XOR != kv)  err = 1;
                }
            }
        }
        printf("Disk set %d is ", ++cases);
        if (err) {
            puts("invalid.");
        } else {
            char buff[65536];
            memset(buff, '0', sizeof(buff));
            int m = 0;
            for (int i = 0, j = 0; i < n; i += S, j++) {
                j %= D;
                for (int k = 0; k < D; k++) {
                    if (k == j) continue;
                    for (int p = i; p < i + S; p++) {
                        buff[m++] = mem[k][p];
                    }
                }
            }
            printf("valid, contents are: ");
            for (int i = 0; i < m; i += 4) {
                int val = 0;
                val |= (buff[i + 0] - '0') << 3;
                val |= (buff[i + 1] - '0') << 2;
                val |= (buff[i + 2] - '0') << 1;
                val |= (buff[i + 3] - '0') << 0;
                printf("%X", val);
            }
            puts("");
        }
    }
    return 0;
}
/*
 
 5 2 5
 E
 xx01011111
 0110111011
 1011011111
 1110101100
 0010010111
 5 2 5
 E
 0001011111
 0110111011
 1011011111
 1110101100
 0010010111
 3 2 5
 E
 0001111111
 0111111011
 xx11011111
 3 5 1
 O
 11111
 11xxx
 x1111
 0
*/
Read More +
解題區►解題區 - UVa

UVa 506 - System Dependencies

Problem

參照《算法競賽入門經典》一書

軟體安裝時，會同時下載所需要的插件包，而插件包的軟體也有可能繼續安裝所需要的插件包。如此遞迴下去把所需要的元件都安裝好。

當安裝一個軟體時，分成使用者安裝和系統安裝兩種，使用者只能刪除自己安裝的軟體，其相依的插件包必須由系統來進行刪除，系統刪除時，會檢查是否還有其他軟體需要相依，若不存在相依，則會將此軟體刪除。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
DEPEND   TELNET TCPIP NETCARD
DEPEND TCPIP NETCARD
DEPEND DNS TCPIP NETCARD
DEPEND  BROWSER   TCPIP  HTML
INSTALL NETCARD
INSTALL TELNET
INSTALL foo
REMOVE NETCARD
INSTALL BROWSER
INSTALL DNS
LIST
REMOVE TELNET
REMOVE NETCARD
REMOVE DNS
REMOVE NETCARD
INSTALL NETCARD
REMOVE TCPIP
REMOVE BROWSER
REMOVE TCPIP
END

Sample Output

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
DEPEND   TELNET TCPIP NETCARD
DEPEND TCPIP NETCARD
DEPEND DNS TCPIP NETCARD
DEPEND  BROWSER   TCPIP  HTML
INSTALL NETCARD
   Installing NETCARD
INSTALL TELNET
   Installing TCPIP
   Installing TELNET
INSTALL foo
   Installing foo
REMOVE NETCARD
   NETCARD is still needed.
INSTALL BROWSER
   Installing HTML
   Installing BROWSER
INSTALL DNS
   Installing DNS
LIST
   NETCARD
   TCPIP
   TELNET
   foo
   HTML
   BROWSER
   DNS
REMOVE TELNET
   Removing TELNET
REMOVE NETCARD
   NETCARD is still needed.
REMOVE DNS
   Removing DNS
REMOVE NETCARD
   NETCARD is still needed.
INSTALL NETCARD
   NETCARD is already installed.
REMOVE TCPIP
   TCPIP is still needed.
REMOVE BROWSER
   Removing BROWSER
   Removing HTML
   Removing TCPIP
REMOVE TCPIP
   TCPIP is not installed.
END

Solution

一道模擬，假想一張 DAG 圖，刪除時暴力檢查其逆向的依存軟體是否存在。

使用 STL 和遞迴可以讓程式更簡單易懂。

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
#include <stdio.h>
#include <map>
#include <queue>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;
vector<string> getArgs(char line[]) {
    stringstream sin(line);
    vector<string> ret;
    string token;
    while (sin >> token)
        ret.push_back(token);
    return ret;
}
map<string, int> name2id;
map<int, string> id2name;
map<int, vector<int> > dependInstall, invDependInstall;
map<int, int> installStatus;
vector<int> installList;
int getId(string s) {
    int &ret = name2id[s];
    if (ret == 0) {
        ret = (int) name2id.size();
        id2name[ret] = s;
    }
    return ret;
}
string getName(int id) {
    return id2name[id];
}
int isDepended(int id) {
    vector<int> &v = invDependInstall[id];
    for (int i = 0; i < v.size(); i++) {
        if (installStatus[v[i]])    return 1;
    }
    return 0;
}
void installSoft(int id, int top) {
    if (installStatus[id] == 0) {
        vector<int> &v = dependInstall[id];
        for (int i = 0; i < v.size(); i++)
            installSoft(v[i], 0);
        printf("   Installing %s\n", getName(id).c_str());
        installStatus[id] = top ? 1 : 2;
        installList.push_back(id);
    }
}
void removeSoft(int id, int top) {
    if ((top == 1 || installStatus[id] == 2) && !isDepended(id)) {
        installStatus[id] = 0;
        printf("   Removing %s\n", getName(id).c_str());
        vector<int> &v = dependInstall[id];
        for (int i = 0; i < v.size(); i++)
            removeSoft(v[i], 0);
        installList.erase(find(installList.begin(), installList.end(), id));
    }
}
int main() {
    char line[2048];
    while (gets(line)) {
        vector<string> args = getArgs(line);
        puts(line);
        if (args[0] == "DEPEND") {
            vector<int> softId;
            for (int i = 1; i < args.size(); i++) {
                softId.push_back(getId(args[i]));
            }
            vector<int> &v = dependInstall[softId[0]];
            for (int i = 1; i < softId.size(); i++) {
                v.push_back(softId[i]);
                invDependInstall[softId[i]].push_back(softId[0]);
            }
        } else if (args[0] == "INSTALL") {
            if (installStatus[getId(args[1])]) {
                printf("   %s is already installed.\n", args[1].c_str());
            } else {
                installSoft(getId(args[1]), 1);
            }
        } else if (args[0] == "REMOVE") {
            if (installStatus[getId(args[1])] == 0) {
                printf("   %s is not installed.\n", args[1].c_str());
            } else if (isDepended(getId(args[1]))) {
                printf("   %s is still needed.\n", args[1].c_str());
            } else {
                removeSoft(getId(args[1]), 1);
            }
        } else if (args[0] == "LIST") {
            for (int i = 0; i < installList.size(); i++) {
                printf("   %s\n", getName(installList[i]).c_str());
            }
        } else if (args[0] == "END") {
            break;
        }
    }
    return 0;
}
/*
 DEPEND   TELNET TCPIP NETCARD
 DEPEND TCPIP NETCARD
 DEPEND DNS TCPIP NETCARD
 DEPEND  BROWSER   TCPIP  HTML
 INSTALL NETCARD
 INSTALL TELNET
 INSTALL foo
 REMOVE NETCARD
 INSTALL BROWSER
 INSTALL DNS
 LIST
 REMOVE TELNET
 REMOVE NETCARD
 REMOVE DNS
 REMOVE NETCARD
 INSTALL NETCARD
 REMOVE TCPIP
 REMOVE BROWSER
 REMOVE TCPIP
 END
 */
Read More +