解題區/解題區 - UVa

UVa 10486 - Mountain Village

Problem

給定一個 n x m 的網格，現在要紮營於格子上，但是每一格的高度不同，希望使用 k 個格子，他們可以藉由上下左右四格相連，找一種方案，使得最低、最高紮營高度差最小。

Input

1
2
3
4
5
6
7
8
9
10
11
12
13
5 10
0 0 3 46 0 46 0 0 12 12
0 0 13 50 49 46 11 10 10 11
0 51 51 49 99 99 89 0 0 10
0 0 48 82 70 99 0 52 13 14
51 50 50 51 70 35 70 10 14 11
6
1
5
10
12
47
50

Output

1
2
3
4
5
6
0
0
3
4
89
99

Solution

由於高度介於 0 到 100 之間，考慮窮舉最低紮營處的高度 l。採用掃描線的方式，依序加入高度較低的地點，直到其中一個連通子圖的節點總數大於等於 k。

為了加速，使用并查集來完成合併連通子圖。

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
#include <stdio.h> 
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 64;
int A[MAXN][MAXN];
vector< pair<int, int> > g[128];
int parent[MAXN*MAXN], weight[MAXN*MAXN];
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;
    if (weight[x] > weight[y])
        weight[x] += weight[y], parent[y] = x;
    else
        weight[y] += weight[x], parent[x] = y;
    return 1;
}
void init(int n)  {
    for (int i = 0; i <= n; i++)
        parent[i] = i, weight[i] = 1;
}
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
int query(int n, int m, int need) {
    int x, y, tx, ty;
    int ret = 0x3f3f3f3f;
    for (int i = 0; i < 100; i++) { // lower
        init(n * m);
        
        int ok = 0;
        for (int j = i; j < 100 && !ok; j++) { // upper
            if (j - i >= ret)
                break;
            for (int k = 0; k < g[j].size() && !ok; k++) {
                x = g[j][k].first, y = g[j][k].second;
                for (int d = 0; d < 4; d++) {
                    tx = x + dx[d], ty = y + dy[d];
                    if (tx < 0 || ty < 0 || tx >= n || ty >= m)
                        continue;
                    if (A[tx][ty] <= j && A[tx][ty] >= i) {
                        joint(x * m + y, tx * m + ty);
                        if (weight[findp(x * m + y)] >= need)
                            ok = 1, ret = min(ret, j - i);
                    }
                }
            }
        }
        
    }
    return ret;
}
int main() {
    int n, m, q, x;
    while (scanf("%d %d", &n, &m) == 2) {
        for (int i = 0; i < 100; i++)
            g[i].clear();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                scanf("%d", &A[i][j]);
                g[A[i][j]].push_back(make_pair(i, j));
            }
        }
        scanf("%d", &q);
        for (int i = 0; i < q; i++) {
            scanf("%d", &x);
            printf("%d\n", query(n, m, x));
        }
    }
    return 0;
}
/*
5 10
0 0 3 46 0 46 0 0 12 12
0 0 13 50 49 46 11 10 10 11
0 51 51 49 99 99 89 0 0 10
0 0 48 82 70 99 0 52 13 14
51 50 50 51 70 35 70 10 14 11
6
1
5
10
12
47
50
*/
Read More +
解題區/解題區 - UVa

UVa 10463 - Aztec Knights

Problem

給定一種特殊的騎士走法，請問在 n x m 格子上，從 (x, y) 到 (a, b) 的步數情況，走訪時不能重複經過相同點。

若能恰好在質數步抵達，輸出最少的步數。如不是質數，輸出合數的最少步數。都還是不行則輸出無法抵達。

Input

1
2
3
5 5 0 0 3 4
5 5 0 0 4 4
5 5 0 0 0 0

Output

1
2
3
CASE# 1: Destination is not reachable.
CASE# 2: The knight takes 2 prime moves.
CASE# 3: The knight takes 0 composite move(s).

Solution

這題麻煩的地方在於恰好在質數抵達，那麼考慮使用 IDA 來完成，在搜索時發生不是在質數步數抵達回傳無解，繼續迭代加深。估價函數為當前座標 (x, y) 到 (a, b) 的最短距離。

在做 IDA 之前，使用 Bfs 查看移動所需步數，若恰好是質數則直接輸出答案，若保證無法抵達終點，輸出無解。最後再進行 IDA 搜索，來加快處理程序。

根據測試，使用的質數步數不大於 11。

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
// IDA, Bfs
#include <stdio.h> 
#include <string.h>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int dx[] = {1, 1, -1, -1, 3, 3, -3, -3};
const int dy[] = {3, -3, 3, -3, 1, -1, 1, -1};
const int px[] = {1, 1, -1, -1, 1, 1, -1, -1};
const int py[] = {1, -1, 1, -1, 1, -1, 1, -1};
int hdist[16][16][16][16];
vector< pair<int, int> > g[16][16];
int move(int n, int m, int x, int y, int kind, int &rx, int &ry) {
    int tx, ty;
    tx = x + dx[kind], ty = y + dy[kind];
    if (tx < 0 || ty < 0 || tx >= n || ty >= m)
        return 0;
    rx = tx, ry = ty;
    tx = x, ty = y;
//	for (int i = 0; i < 2; i++) {
//		tx = tx + px[kind], ty = ty + py[kind];
//		if (tx < 0 || ty < 0 || tx >= n || ty >= m)
//			return 0;
//	}
    return 1;
}
void moveBfs(int n, int m, int sx, int sy) {
    int x, y, tx, ty;
    int dist[16][16] = {};
    const int INF = 0x3f3f3f3f;
    queue<int> X, Y;
    
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            dist[i][j] = INF;
            
    X.push(sx), Y.push(sy), dist[sx][sy] = 0;
    while (!X.empty()) {
        x = X.front(), y = Y.front();
        X.pop(), Y.pop();
        for (int i = 0; i < 8; i++) {
            if (move(n, m, x, y, i, tx, ty)) {
                if (dist[tx][ty] > dist[x][y] + 1) {
                    dist[tx][ty] = dist[x][y] + 1;
                    X.push(tx), Y.push(ty);
                }
            }
        }
    }
    
    // record sssp
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            hdist[sx][sy][i][j] = dist[i][j];
        }
    }
}
#define MAXL (100>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
int mark[MAXL];
int P[5500], Pt = 0;
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 100;
    for(i = 2; i <= n; i++) {
        if(!GET(i)) {
            for (k = n/i, j = i*k; k >= i; k--, j -= i)
                SET(j);
            P[Pt++] = i;
        }
    }
}
// IDA
int ida_depth, solved;
int used[16][16];
int IDA(int x, int y, int ex, int ey, int dep, int hv) {
    if (hv == 0) {
        if (!GET(dep)) {
        	solved = 1;
        	return dep;
        }
        return 0x3f3f3f3f;
        return dep;
    }
    if (dep + hv > ida_depth)
        return dep + hv;
    int back = 0x3f3f3f3f, shv, tmp;
    for (int i = 0; i < g[x][y].size(); i++) {
    	int tx = g[x][y][i].first, ty = g[x][y][i].second;
        shv = hdist[tx][ty][ex][ey];
        
        if (used[tx][ty])
        	continue;
        	
        used[tx][ty] = 1;
        tmp = IDA(tx, ty, ex, ey, dep + 1, shv);
        used[tx][ty] = 0;
        
        back = min(back, tmp);
        if (solved) return back;
    }
    return back;
}
int main() {
    sieve();
    int n, m, sx, sy, ex, ey;
    int cases = 0;
    while (scanf("%d %d %d %d %d %d", &n, &m, &sx, &sy, &ex, &ey) == 6) {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                moveBfs(n, m, i, j);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                g[i][j].clear();
                for (int k = 0; k < 8; k++) {
                    int tx, ty;
                    if (move(n, m, i, j, k, tx, ty))
                        g[i][j].push_back(make_pair(tx, ty));
                }
            }
        }
        
//		printf("Bfs %d\n", hdist[sx][sy][ex][ey]);
//		for (int i = 0; i < n; i++, puts(""))
//			for (int j = 0; j < m; j++)
//				printf("%d ", hdist[sx][sy][i][j] == 0x3f3f3f3f ? -1 : hdist[sx][sy][i][j]);
        
        printf("CASE# %d: ", ++cases);
        
        if (hdist[sx][sy][ex][ey] > 1 && hdist[sx][sy][ex][ey] < 100 && !GET(hdist[sx][sy][ex][ey])) {
            printf("The knight takes %d prime moves.\n", hdist[sx][sy][ex][ey]);
            continue;
        }
                
        solved = 0;
        if (hdist[sx][sy][ex][ey] != 0x3f3f3f3f && (sx != ex || sy != ey)) {
            memset(used, 0, sizeof(used)); 
            
            used[sx][sy] = 1;
            ida_depth = 0;
            for (int i = 0; i < Pt && P[i] < 11; i++) {
                if (P[i] < ida_depth)
                    continue;
                ida_depth = P[i];
                ida_depth = IDA(sx, sy, ex, ey, 0, hdist[sx][sy][ex][ey]);
                
                if (solved) {
                    printf("The knight takes %d prime moves.\n", P[i]);
                    break;
                }
            }
        }
        if (!solved) {
            if (hdist[sx][sy][ex][ey] == 0x3f3f3f3f)
                printf("Destination is not reachable.\n");
            else
                printf("The knight takes %d composite move(s).\n", hdist[sx][sy][ex][ey]);
        }
    }
    return 0;
} 
/*
5 7 2 2 3 1
5 5 0 0 3 4
5 5 0 0 4 4
5 5 0 0 0 0
8 4 4 0 3 2
4 8 1 1 3 5
5 7 2 2 3 1
7 8 0 7 0 5
7 5 1 4 0 4
5 6 1 4 0 2
6 4 0 2 0 1
8 8 1 0 2 7
8 5 0 1 6 1
7 8 1 5 1 4
*/
Read More +
解題區/解題區 - UVa

UVa 10454 - Trexpression

Problem

給一個只有加法、乘法和括弧的運算式，在不改變最後的答案下，有多少種不同的運算順序 (不同的 parse tree)。

Input

1
2
3
4
1+2+3+4
(1+2)+(3+4)
1+2+3*4
1+2+(3*4)

Output

1
2
3
4
5
1
2
2

Solution

類似矩陣鏈乘積的 O(n^3) 解法。

dp[l, r] 表示表達式 exp[l, r] 正確的方法數。當運算式存在加法時，不能拆分乘法運算。只剩下乘法運算時，才能拆分乘法運算。

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
#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
const int MAXN = 256;
long long dp[MAXN][MAXN];
char s[MAXN];
long long dfs(int l, int r) {
    if (l == r)			return 1;
    if (dp[l][r] != -1)	return dp[l][r];
    long long &ret = dp[l][r];
    ret = 0;
    int left = 0, o1 = 0, o2 = 0;
    for (int i = l; i <= r; i++) {
        if (s[i] == '(')
            left++;
        else if (s[i] == ')')
            left--;
        else {
            if (left == 0) {
                if (s[i] == '+')	
                    o1 = 1;
                if (s[i] == '*')
                    o2 = 1;
            }				
        }
    }
    if (o1 == 0 && o2 == 0)
        ret += dfs(l+1, r-1);
    for (int i = l; i <= r; i++) {
        if (s[i] == '(')
            left++;
        else if (s[i] == ')')
            left--;
        else {
            if (left == 0) {
                if (s[i] == '+')
                    ret += dfs(l, i-1) * dfs(i+1, r);
                if (s[i] == '*' && o1 == 0)
                    ret += dfs(l, i-1) * dfs(i+1, r);
            }				
        }
    }
    return ret;
}
int main() {
    while (gets(s)) {
        memset(dp, -1, sizeof(dp));
        long long v = dfs(0, strlen(s) - 1);
        printf("%lld\n", v);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 10413 - Crazy Savages

Problem

瘋狂的島嶼上有 n 個野蠻人、m 個山洞，山洞呈現環狀分佈。

每個野蠻人一開始各自在自己的洞窟 Ci，每隔一天就會移動到下 Pi 個山洞，在島上待 Li 天後就會死亡。

兩個野蠻人若剛好移動到相同洞窟，則會發生爭吵，請問至少要幾個洞窟，才能不發生爭吵。

Input

1
2
3
4
5
6
7
8
9
10
11
2
3
1 3 4
2 7 3
3 2 1
5
1 2 14
4 4 6
8 5 9
11 8 13
16 9 10

Output

1
2
6
33

Solution

窮舉洞窟數量 m，檢查是否存在爭吵。

檢查任兩個野蠻人 i, j 是否會在生存時間內相遇，假設會在第 k 天相遇，滿足公式

1
2
ci + k * pi = a * m  --- (1)
cj + k * pj = b * m  --- (2)

將公式整理後

1
2
3
(2)-(1) 	=> (ci - cj) + k * (pi - pj) = m * (a - b)
            => (a - b) * m + k * (pj - pi) = ci - cj
check k in [0, min(L[i], L[j])] has a

檢查 k 最小為多少，使得等式解存在。

套用擴充歐幾里德算法，得到 ax + by = gcd(x, y) 的第一組解 (a, b)，其 a, b 的參數式為

1
2
3
4
5
g = gcd(x, y)
a = a + lcm(x, y)/x * k
b = b + lcm(x, y)/y * k
=> a = a + y / g * k
=> b = b + x / g * k

最小化 a 參數，滿足 a >= 0，隨後檢查可行解即可。

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
#include <stdio.h> 
#include <algorithm>
#include <math.h>
using namespace std;
const int MAXN = 32;
const int INF = 0x3f3f3f3f;
int C[MAXN], P[MAXN], L[MAXN];
// a x + by = g
void exgcd(int x, int y, int &g, int &a, int &b) {
    if (y == 0)
        g = x, a = 1, b = 0;
    else
        exgcd(y, x%y, g, b, a), b -= (x/y) * a;
}
int hasCollision(int m, int n) {
    // assume m caves arranged in a circle
    // ci + k * pi = a * m  --- (1)
    // cj + k * pj = b * m  --- (2)
    // (2)-(1) 	=> (ci - cj) + k * (pi - pj) = m * (a - b)
    //			=> (a - b) * m + k * (pj - pi) = ci - cj
    // check k in [0, min(L[i], L[j])] has a solution.
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            int x = P[j] - P[i], y = m, z = C[i] - C[j];
            int a, b, g;
            int limitR = min(L[i], L[j]), limitL = 0;
            exgcd(x, y, g, a, b);
        
            if (z%g)	continue;
            a = a * (z / g);
            // ax + by = z
            // a = a + lcm(x, y)/x * k, b = b + lcm(x, y)/y * k
            // a = a + y / g * k, b = b + x / g * k
            // minmum a, a >= 0
            if (g < 0)	g = -g;
            a = (a%(y/g) + y/g) % (y/g);
            if (a <= limitR)
                return true;
        }
    }
    return false;
}
int main() {
    int testcase, n;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        
        int m = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d %d %d", &C[i], &P[i], &L[i]);
            m = max(m, C[i]);
        }
            
        int ret = -1;
        for (int i = m; i < 99999999; i++) {
            
            if (!hasCollision(i, n)) {
                ret = i;
                break;
            }
        }
        printf("%d\n", ret);
    }
    return 0;
}
/*
2
3
1 3 4
2 7 3
3 2 1
5
1 2 14
4 4 6
8 5 9
11 8 13
16 9 10
*/
Read More +
解題區/解題區 - UVa

UVa 10412 - Big Big Trees

Problem

有隻猴子在樹間，每一棵樹有平行的分支，猴子可以在兩棵樹的分支端點跳躍，並且跳躍距離不超過歐幾里德距離 K，並且跳躍的時候只能跳端點的直線上，同時不能撞到其他分支，否則視如跳躍失敗。

猴子從樹幹走到分支端點、端點走到樹幹是需要計算步行花費，請問從第一棵樹走到最後一棵樹，最少的步行花費為何。

Input

1
2
3
4
5
6
7
8
2
2 7 3
4 3 2 2 0
5 3 0 1 0 0
3 50 40
4 15 3 16 10
8 12 12 12 21 12 15 6 14
13 15 23 20 18 14 1 21 9 9 18 23 10 4

Output

1
2
5
28

Solution

分支數量很少，直接暴力嘗試跳躍的可行性。使用外積解決線段交問題，隨後計算跳躍的最少花費，記錄狀態 dp[i] 表示從第一棵樹走到第 i 棵樹的最少步行成本。

特別小心當跳躍都無法時，可以走在地面上，由於這一點掛了好多 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
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
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <string.h>
#include <assert.h>
#include <vector>
using namespace std;
#define eps 1e-8
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);
    }
};
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(), int l=0):s(a), e(b), label(l) {
//		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;
    }
    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 (as == at && bs == bt)
        return as == bs;
    if (as == at)
        return onSeg(bs, bt, as);
    if (bs == bt)
        return onSeg(as, at, bs);
    if(cross(as, at, bs) * cross(as, at, bt) <= 0 &&
        cross(at, as, bs) * cross(at, as, bt) <= 0 &&
        cross(bs, bt, as) * cross(bs, bt, at) <= 0 &&
        cross(bt, bs, as) * cross(bt, bs, at) <= 0)
        return 1;
    return 0;
}
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);
}
const double pi = acos(-1);
int cmpZero(double v) {
    if (fabs(v) > eps) return v > 0 ? 1 : -1;
    return 0;
}
const int MAXN = 1024;
int HN[MAXN], H[MAXN][32];
int main() {
    int testcase, N, M, K;
    
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d", &N, &M, &K);
        for (int i = 0; i < N; i++) {
            scanf("%d", &HN[i]);
            for (int j = 0; j < HN[i]; j++)
                scanf("%d", &H[i][j]);
        }
        int dp[MAXN];
        
        memset(dp, 63, sizeof(dp));
        dp[0] = 0;
        
        for (int i = 0; i+1 < N; i++) {
//			printf("%d\n", dp[i]);
            for (int j = 0; j < HN[i]; j++) {
                for (int k = 0; k < HN[i+1]; k++) {
                    int dx, dy;
                    dx = M - H[i][j] - H[i+1][k];
                    dy = abs(j - k);
                    if (dx * dx + dy * dy > K * K)
                        continue;	
//					printf("%d %d, %d %d\n", j, k, dx, dy);
                    int ok = 1;
                    for (int p = 0; p < HN[i]; p++) {
                        if (p == j)	continue;
                        if (intersection(Pt(H[i][j], j), Pt(M-H[i+1][k], k), Pt(0, p), Pt(H[i][p], p)))
                            ok = 0;
                    }
                    for (int p = 0; p < HN[i+1]; p++) {
                        if (p == k)	continue;
                        if (intersection(Pt(H[i][j], j), Pt(M-H[i+1][k], k), Pt(M, p), Pt(M-H[i+1][p], p)))
                            ok = 0;
                    }
                    if (ok) {
//						printf("--- %d %d %d\n", j, k, H[i][j], H[i+1][k]);
                        dp[i+1] = min(dp[i+1], dp[i] + H[i][j] + H[i+1][k]);
                    }
                }	
            }
            dp[i+1] = min(dp[i+1], dp[i] + M); // WTF !!!!!!!!!!!!!!! 
        }
        
        printf("%d\n", dp[N-1]);
    }
    return 0;
}
/*
1
5 10 12
1 2
3 2 1 4
8 2 4 4 1 4 0 0 0
8 1 1 2 0 4 1 3 3
10 1 4 0 1 1 1 1 2 1 4
999
5 10 3
2 0 2
1 1
10 1 2 0 1 2 2 0 4 4 4
9 3 1 2 1 2 1 4 1 3
8 0 1 2 1 3 1 0 0
2
2 7 3
4 3 2 2 0
5 3 0 1 0 0
3 50 40
4 15 3 16 10
8 12 12 12 21 12 15 6 14
13 15 23 20 18 14 1 21 9 9 18 23 10 4
999
3 5 100
3 0 0 1
2 0 0
3 0 0 1
2 7 5
1 3
4 3 3 2 1
2 10 2
1 4
2 0 4
2 10 4
1 4
2 0 4
2 10 2
2 0 4
2 0 4
*/
Read More +
解題區/解題區 - UVa

UVa 10351 - Cutting Diamonds

Problem

給一個橢球的三個參數，一刀縱切橢球，問切割橢球的截面積為何。

Input

1
2
7 6 4 8 6 4
4 8 8 8 8 8

Output

1
2
3
4
Set #1
8.246681
Set #2
50.265482

Solution

回顧積分公式，得到橢圓面積。將橢球固定一個參數，調整計算截面積。公式如代碼中所附。

$$\frac{x^2}{a^2} + \frac{y^2}{b^2} = 1 \\ \text{area } = ab\pi \\ \frac{x^2}{a^2} + \frac{y^2}{b^2} + \frac{z^2}{c^2} = 1 \\ \frac{x^2}{(a \sqrt{1 - z^2 / c^2})^2} + \frac{y^2}{(b \sqrt{1 - z^2 / c^2})^2} = 1 \\ \text{cross-sectional area} = ab (1 - z^2 / c^2) \pi \\$$ 
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
#include <stdio.h> 
#include <math.h>
using namespace std;
/*
    x^2 / a^2 + y^2 / b^2 = 1 
        area = ab pi
    
    x^2 / a^2 + y^2 / b^2 + z^2 / c^2 = 1
    
    x^2 / (a \sqrt{1 - z^2 / c^2})^2 + y^2 / (b \sqrt{1 - z^2 / c^2})^2 = 1;
    cross-sectional area = ab (1 - z^2 / c^2) pi
    
    volume 	ab (1 - z^2 / c^2) pi dz
            ab pi (z - z^3 / 3 / c^2), for z in [l, r]
*/
const double pi = acos(-1);
int main() {
    int a, b, c, ra, rb, rc;
    int cases = 0;
    while (scanf("%d %d %d %d %d %d", &ra, &rb, &rc, &a, &b, &c) == 6) {
        printf("Set #%d\n", ++cases);
        double ta, tb, tc, l, r;
        if (ra > a || rb > b || rc > c) {
            printf("%.6lf\n", 0.0); // WTF
            continue;
        }
        if (ra < a) {
            ta = b/2.0, tb = c/2.0, tc = a/2.0;
            r = a/2.0, l = r - fabs(a - ra);
        } else if (rb < b) {
            ta = a/2.0, tb = c/2.0, tc = b/2.0;
            r = b/2.0, l = r - fabs(b - rb);
        } else if (rc < c) {
            ta = a/2.0, tb = b/2.0, tc = c/2.0;
            r = c/2.0, l = r - fabs(c - rc);
        } else {
            printf("%.6lf\n", 0.0); // WTF
            continue;
        }
        double area;
        area = ta * tb * pi * (1 - l*l/tc/tc);
        printf("%.6lf\n", area);
    }
    return 0;
}
/*
7 6 4 8 6 4
4 8 8 8 8 8
2 6 4 8 6 4
8 6 4 8 6 4
*/
Read More +
解題區/解題區 - UVa

UVa 10280 - Old Wine Into New Bottles

Problem

給予 n 種酒瓶，每一種酒瓶有其裝酒的容積上下限 [min, max] 毫升，請問將 m 公升的酒裝入酒瓶，最後剩餘的最少量為多少。

每一種酒瓶可以無限使用。

Input

1
2
3
4
5
6
7
8
9
2
10 2
4450 4500
725 750
10000 2
4450 4500
725 750

Output

1
2
3
250
0

Solution

這一題需要剪枝，無法單純地運行背包 dp，單純的背包 dp 很容易造成 TLE。

發現到只考慮使用一種酒瓶，那麼當酒量大於某個定值後，保證都能裝完。假設使用單一酒瓶的數量為 k 個以上時，能裝出所有量，則能覆蓋的區間為

1
[min, max], ..., [k*min, k*max], [(k+1)*min, (k+1)*max]

當第 k+1 個區間的左端點小於第 k 個區間的右端點時，可以得到接下來的所有區間都會發生重疊。推導得到 (k+1)*min >= k*max 最後條件 k >= min / (max - min)。

滿足保證能裝出，直接輸出答案 0，否則做背包 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
#include <stdio.h> 
#include <algorithm>
#include <string.h>
using namespace std;
#define MAXL (1000000>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
int mark[MAXL];
/*
    k bottles
    [min, max], ..., [k*min, k*max], [(k+1)*min, (k+1)*max]
    
    always have solution for [k*min, k*max], [(k+1)*min, (k+1)*max] 
    sat. (k+1)*min >= k*max 
            k >= min / (max - min)
    all interval cover each other after k-bottles.
*/
const int MAXN = 128;
int mx[MAXN], mn[MAXN];
int main() {
    int testcase, L, N;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &L, &N);
        L *= 1000;
        
        int lower_full = 0x3f3f3f3f; 
        for (int i = 0; i < N; i++) {
            scanf("%d %d", &mn[i], &mx[i]);
            lower_full = min(lower_full, mn[i] * mn[i] / (mx[i] - mn[i]));
        }
        
        if (L >= lower_full) {
            puts("0");
            if (testcase)
                puts("");
            continue;
        }
        
        // limit L <= 4500 * 4500 / (4500 * 0.01)
        int A[4505] = {}, ret = 0;
        
        for (int i = 0; i < N; i++)
            for (int j = mn[i]; j <= mx[i]; j++)
                A[j] = 1;
            
        memset(mark, 0, sizeof(mark)); 
        SET(0);
        for (int i = 1; i <= 4500; i++) {
            if (A[i] == 0)
                continue;
            for (int j = i, k = 0; j <= L; j++, k++) {
                if (GET(k))
                    SET(j), ret = max(ret, j);
            }
        }
        
        printf("%d\n", L - ret);
        if (testcase)
            puts("");
    }
    return 0;
}
/*
2
10 2
4450 4500
725 750
10000 2
4450 4500
725 750
*/
Read More +
解題區/解題區 - UVa

UVa 1502 - GRE Words

Problem

依序背單字，下一個單字中要出現當前單字為 substring 的情況，每一個單字都有各自的權重，求背一次能得到的最高權重總合為多少。

如範例輸入背的順序為 a -> ab -> abb -> abbab 答案為 1 + 2 + 3 + 8 = 14。

Sample Input

1
2
3
4
5
6
7
1
5
a 1
ab 2
abb 3
baba 5
abbab 8

Sample Output

1
Case #1: 14

Solution

這一題的測資有問題，輸入中出現非小寫字母，導致存取發生錯誤，部分程序沒有考慮這一點，居然就通過了？
一群人 Invalid Memory Access 通過，而我因寫法比較不同成了 RE 下亡魂，測試數據格式錯誤啊！坑爹啊，害我掛載好多 assert 抓哪裡溢出 …

原本想說是一道有趣的 AC 自動機複習，將 fail 指針 (suffix link) 整理成另一棵樹，對其 fail tree 壓樹 (走訪)，套上線段樹等數據結構，就能支持多字串匹配的數據查找。當匹配時將會一直攀爬 fail 指針，最後爬到 root，中間經過的節點都是匹配的字串，也因此單看 fail 指針，也肯定是 tree。

在走訪時，會匹配 fail link 上的所有節點 (都是其 suffix string)。dp[i] 表示使用第 i 個字串為背單字序列結尾的最大權重，則 dp[i] = max(dp[j]) + w，其中滿足 j < i 且 word[j] 是 word[i] 的 substring。

窮舉第 i 字符串的後綴匹配節點，找尋匹配節點藉由 fail link 到 root 上節點的最大值 (max(dp[j]))。

利用線段樹完成區間最大值更新、單點查詢 (找尋節點到 root 的最大值，更新一個點的權重時，相當於作區間最大值更新，藉由壓樹其子樹被表示成區間)。

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
// NOTES: has error test data, there are some characters which aren't lowercase letters.
// FUCK
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <map>
#include <algorithm>
#include <assert.h>
#include <assert.h>
#pragma comment( linker, "/STACK:1024000000,1024000000")
using namespace std;
const int MAXCHAR = 26;
const int MAXNODE = 1048576;
class ACmachine {
public:
    struct Node {
        Node *next[MAXCHAR], *fail;
        int cnt, val, id, nid;
        void init() {
            fail = NULL;
            cnt = val = 0;
            nid = id = -1;
            memset(next, 0, sizeof(next));
        }
    } nodes[MAXNODE];
    Node *root;
    int size;
    vector<int> fg[MAXNODE];
    Node* getNode() {
        Node *p = &nodes[size++];
        p->init(), p->nid = size-1;
        assert(size < MAXNODE);
        fg[p->nid].clear();
        return p;
    }
    void init() {
        size = 0;
        root = getNode();
    }
    int toIndex(char c) {
    	assert(c - 'a' >= 0 && c - 'a' < MAXCHAR);
        return c - 'a';
    }
    void dfs(Node *p, Node *q) {
        for (int i = 0; i < MAXCHAR; i++) {
            if (q->next[i]) {
                Node *u = p->next[i], *v = q->next[i];
                if (u == NULL)
                    p->next[i] = getNode(), u = p->next[i];
                u->cnt |= v->cnt;
                dfs(u, v);
            }
        }
    }
    void merge(const ACmachine &other) {
        dfs(root, other.root);
    }
    void insert(const char str[], int sid) {
        Node *p = root;
        for (int i = 0, idx; str[i]; i++) {
            idx = toIndex(str[i]);
            if (p->next[idx] == NULL)
                p->next[idx] = getNode();
            p = p->next[idx];
        }
        p->cnt = 1;
        if (sid >= 0)	p->id = sid;
    }
    int find(const char str[]) {
        Node *p = root;
        for (int i = 0, idx; str[i]; i++) {
            idx = toIndex(str[i]);
            if (p->next[idx] == NULL)
                p->next[idx] = getNode();
            p = p->next[idx];
        }
        return p->cnt;
    }
    void build() { // AC automation    
        queue<Node*> Q;
        Node *u, *p;
        Q.push(root), root->fail = NULL;
        while (!Q.empty()) {
            u = Q.front(), Q.pop();
            if (u != root) {
            	assert(u->fail != NULL);
            	assert(u->nid != u->fail->nid);
            	fg[u->nid].push_back(u->fail->nid);
            	fg[u->fail->nid].push_back(u->nid);
            }
            for (int i = 0; i < MAXCHAR; i++) {
                if (u->next[i] == NULL)
                    continue;
                Q.push(u->next[i]);
                p = u->fail;
                while (p != NULL && p->next[i] == NULL)
                    p = p->fail;
                if (p == NULL || p->next[i] == NULL)
                    u->next[i]->fail = root;
                else
                    u->next[i]->fail = p->next[i];
                u->next[i]->val = u->next[i]->fail->val + u->next[i]->cnt;
                u->next[i]->id = u->next[i]->fail->id | u->next[i]->id;
            }
        }
    }
    int query(const char str[]) {
        Node *u = root, *p;
        int matched = 0;
        for (int i = 0, idx; str[i]; i++) {
            idx = toIndex(str[i]);
            while (u->next[idx] == NULL && u != root)
                u = u->fail;
            u = u->next[idx];
            u = (u == NULL) ? root : u;
            p = u;
            matched += p->val;
        }
        return matched;
    }
    void free() {
        return ;
        // owner memory pool version
        queue<Node*> Q;
        Q.push(root);
        Node *u;
        while (!Q.empty()) {
            u = Q.front(), Q.pop();
            for (int i = 0; i < MAXCHAR; i++) {
                if (u->next[i] != NULL) {
                    Q.push(u->next[i]);
                }
            }
            delete u;
        }
    }
};
const int MAXN = 1048576;
class SegmentTree {
public:
    struct Node {
        long long mx;
        pair<int, long long> label;
        void init() {
            mx = -1LL<<60;
            label = make_pair(0, 0);
        }
    } nodes[MAXN];
    void pushDown(int k, int l, int r) {
        int mid = (l + r)/2;
        if (nodes[k].label.first) {
            maxUpdate(k<<1, l, mid, nodes[k].label.second);
            maxUpdate(k<<1|1, mid+1, r, nodes[k].label.second);
            nodes[k].label = make_pair(0, 0); // cancel
        }
    }
    void pushUp(int k) {
        nodes[k].mx = max(nodes[k<<1].mx, nodes[k<<1|1].mx);
    }
    void build(int k, int l, int r) { 
        nodes[k].init();
        if (l == r) {
            nodes[k].mx = 0;
            return ;
        }
        int mid = (l + r)/2;
        build(k<<1, l, mid);
        build(k<<1|1, mid+1, r);
        pushUp(k);
    } 
    // operator, assign > add
    void maxUpdate(int k, int l, int r, long long val) {
        if (nodes[k].label.first)
            val = max(val, nodes[k].label.second);
        nodes[k].label = make_pair(1, val);
        nodes[k].mx = max(nodes[k].mx, val);
    }
    void assign(int k, int l, int r, int x, int y, int val) {
        if (x <= l && r <= y) {
            maxUpdate(k, l, r, val);
            return;
        }
        pushDown(k, l, r);
        int mid = (l + r)/2;
        if (x <= mid)
            assign(k<<1, l, mid, x, y, val);
        if (y > mid)
            assign(k<<1|1, mid+1, r, x, y, val);
        pushUp(k);
    }
    // query 
    long long r_mx;
    void qinit() {
        r_mx = -1LL<<60;
    }
    void query(int k, int l, int r, int x, int y) {
        if (x <= l && r <= y) {
            r_mx = max(r_mx, nodes[k].mx);
            return ;
        }
        pushDown(k, l, r);
        int mid = (l + r)/2;
        if (x <= mid)
            query(k<<1, l, mid, x, y);
        if (y > mid)
            query(k<<1|1, mid+1, r, x, y);
    }
};
ACmachine ac;
SegmentTree tree;
vector<string> words;
vector<int> wvals;
char s[1048576];
int bPos[MAXN], ePos[MAXN], inIdx;
void prepare(int u, int p) {
    bPos[u] = ++inIdx;
    for (int i = 0; i < ac.fg[u].size(); i++) {
        if (ac.fg[u][i] == p)	continue;
        prepare(ac.fg[u][i], u);
    }
    ePos[u] = inIdx;
} 
void solve() {
    for (int i = 0; i < ac.size; i++)
        bPos[i] = ePos[i] = 0;
    inIdx = 0;
    for (int i = 0; i < ac.size; i++) {
        if (bPos[i] == 0) {
            prepare(i, -1); // interval [1, inIdx]
        }
    }
            
    assert(inIdx < MAXN/2);
    tree.build(1, 1, inIdx);
    
    long long ret = 0;
    for (int i = 0; i < words.size(); i++) {
        ACmachine::Node *u = ac.root;
        int idx;
        long long dpval = 0;
        for (int j = 0; j < words[i].length(); j++) {
            idx = ac.toIndex(words[i][j]);
            while (u->next[idx] == NULL && u != ac.root)
                u = u->fail;
            u = u->next[idx];
            u = (u == NULL) ? ac.root : u;
            
            tree.qinit();
            tree.query(1, 1, inIdx, bPos[u->nid], bPos[u->nid]);
            dpval = max(dpval, tree.r_mx);
        }
        dpval += wvals[i];
        tree.assign(1, 1, inIdx, bPos[u->nid], ePos[u->nid], dpval);
        ret = max(ret, dpval);
    }
    printf("%lld\n", ret);
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    int testcase, cases = 0;
    int N, val;
    scanf("%d", &testcase);
    while (testcase--) {
    	scanf("%d", &N);
    	    	
       	ac.init();
       	words.clear(), wvals.clear();
       	for (int i = 0; i < N; i++) {
       		scanf("%s %d", s, &val);
       		ac.insert(s, i);
       		words.push_back(s), wvals.push_back(val);
       	}
       	
       	ac.build();
       	
       	printf("Case #%d: ", ++cases);
       	solve(); 
       	
        ac.free();
    }
    return 0;
}
/*
999
4
abbaaa 49
bba 41
ba 19
bbba 20
8
abbaaa 49
bba 41
ba 19
bbba 20
abbbabaaa 21
b 47
ababba 26
a 0
3
abaab 35
ab 9
abaabaaabbabababaaab 35
8
aabbbbbababbaaaab 14
abaabbaaaaaabbaabbba 13
babaaababaaaaabababa 17
abaab 35
ab 9
abaabaaabbabababaaab 35
bbbaaa 31
aabab 34
32
aa 19
bababbabbbaabaaaab 40
aabbbaaaaaa 48
ababaaabbabbbaabbb 38
a 42
bbbbbaabbbaa 10
baabbbababaab 41
aabbabbabba 28
baaab 3
aaaaaaaaa 15
bbbabbababaaabab 16
aab 18
baaab 2
abbbab 2
bababa 4
bbabbbbbaabbaaaababb 35
bbbaabba 34
bbbb 24
bbbb 17
babbbabbababababaa 9
ababaaaa 38
bbbb 3
bba 31
aabaabaaa 34
aabbbbbaababaa 41
aabbbaabbbabaababbbb 45
abbbaabbababab 37
ababbaabb 3
bbabbbbbaba 8
a 10
babbabaabbbbab 34
bbababaaaaaaaaa 5
 */
Read More +
解題區/解題區 - UVa

UVa 1398 - Meteor

Problem

進行天文觀測，天空上有 n 個流星，以及拍攝的區域。

給定每一個流星的起始位置與速度，請問在哪一個時刻可以拍到最多顆流星在拍攝區域內部。

Sample Input

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

Sample Output

1
2
1 
2

Solution

將每一個流星進入和離開拍攝區域的時間求出，並且組合成 (enter_time, 1), (leave_time, -1) 的方式，根據時間由小排到大，利用掃描線算法統計累計的最大值即可。

求流星進出區域的時間，可以將 x, y 座標分開考慮，對進入時間取最大值、離開時間取最小值。

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
// sweep line algorithm
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int LCM = 2520; // gcd(1, 2, 3, ..., 10) = 2520, /vx, /vy, vx, vy <= 10
int W, H;
pair<int, int> getTime(int sx, int sy, int vx, int vy) {
    int enter = 0, leave = INF;
    if (vx == 0) {
        if (sx <= 0 || sx >= W)
            leave = 0;
    } else if (vx < 0) {
        enter = max(enter, (sx - W) * LCM / (-vx));
        leave = min(leave, (sx - 0) * LCM / (-vx));
    } else {
        enter = max(enter, (0 - sx) * LCM / (vx));
        leave = min(leave, (W - sx) * LCM / (vx));
    }
    if (vy == 0) {
        if (sy <= 0 || sy >= H)
            leave = 0; 
    } else if (vy < 0) {
        enter = max(enter, (sy - H) * LCM / (-vy));
        leave = min(leave, (sy - 0) * LCM / (-vy));
    } else {
        enter = max(enter, (0 - sy) * LCM / (vy));
        leave = min(leave, (H - sy) * LCM / (vy));
    }
    return make_pair(enter, leave);
}
int main() {
    int testcase, N;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &W, &H);
        scanf("%d", &N);
        
        vector< pair<int, int> > D;
        for (int i = 0; i < N; i++) {
            int sx, sy, vx, vy;
            scanf("%d %d %d %d", &sx, &sy, &vx, &vy);
            pair<int, int> t = getTime(sx, sy, vx, vy);
            if (t.first < t.second) {
                D.push_back(make_pair(t.first, 1));
                D.push_back(make_pair(t.second, -1));
            }
        }
        
        sort(D.begin(), D.end());
        int ret = 0;
        for (int i = 0, s = 0; i < D.size(); i++) {
            s += D[i].second;
            ret = max(ret, s);
        }
        printf("%d\n", ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 1342 - That Nice Euler Circuit

Problem

一筆畫完成一個簡單多邊形，請問有多少個區域。

Sample Input

1
2
3
4
5
5
0 0 0 1 1 1 1 0 0 0 
7 
1 1 1 5 2 1 2 5 5 1 3 5 1 1 
0

Sample Output

1
2
Case 1: There are 2 pieces. 
Case 2: There are 5 pieces.

Solution

利用尤拉公式$V - E + F = 2$ 來完成，藉由線段交找到所有頂點集合，去除掉重複點後，檢查邊的數量，如此一來就可以找到面的數量。

特別小心共線計算。

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
// Euler characteristic, V - E + F = 2
#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-8
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 {
    	return !(a == *this);
    }
    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(vector<Pt> &p, Pt q) {
    int i, j, cnt = 0;
    int n = p.size();
    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;
}
double polygonArea(vector<Pt> &p) {
    double area = 0;
    int n = p.size();
    for(int i = 0; i < n;i++)
        area += p[i].x * p[(i+1)%n].y - p[i].y * p[(i+1)%n].x;
    return fabs(area) /2;
}
Pt projectLine(Pt as, Pt ae, Pt p) {
    double a, b, c, v;
    a = as.y - ae.y, b = ae.x - as.x;
    c = - (a * as.x + b * as.y);
    v = a * p.x + b * p.y + c;
    return Pt(p.x - v*a / (a*a+b*b), p.y - v*b/ (a*a+b*b));
}
// maybe collinear !!!!!!!!
int main() {
    const int MAXN = 305;
    int n, cases = 0;
    Pt D[MAXN];
    while (scanf("%d", &n) == 1 && n) {		
        int V = 0, E = 0; 
        vector<Pt> SV;
        
        for (int i = 0; i < n; i++)
            D[i].read(), SV.push_back(D[i]);
        for (int i = 0; i+1 < n; i++) {
            for (int j = i+1; j+1 < n; j++) {
                if (intersection(D[i], D[i+1], D[j], D[j+1])) {
                    Pt p = getIntersect(Seg(D[i], D[i+1]), Seg(D[j], D[j+1]));
                    SV.push_back(p);
                }
            }
        }
        
        sort(SV.begin(), SV.end());
        SV.resize(unique(SV.begin(), SV.end()) - SV.begin());
        V = SV.size(), E = n - 1;
        for (int i = 0; i < SV.size(); i++) {
            for (int j = 0; j+1 < n; j++) {
                if (onSeg(D[j], D[j+1], SV[i]) && SV[i] != D[j] && SV[i] != D[j+1])
                    E++;
            }
        }
//		printf("%d %d\n", E, V);
        int ret = E - V + 2; // V - E + F = 2, F = E - V + 2
        printf("Case %d: There are %d pieces.\n", ++cases, ret);
    }
    return 0;
}
/*
7 
1 1 1 5 2 1 2 5 5 1 3 5 1 1 
0
*/
Read More +