解題區/解題區 - UVa

UVa 10848 - Make Palindrome Checker

Problem

檢查生的測資是否符合規格，規則共有七條，分別告知每一條是否符合規格。

  1. 第一個字串必須為小寫字母構成，其長度最多為 1000，第二個字串表示一個不大於 1000 的非負整數。第三個字串必須為小寫字母構成，其長度最多為 2000。
  2. 規則 1 && 第三個字串必須為回文。
  3. 規則 1 && 第一個字串出現的英文字母類型都必須在第三字串中出現。
  4. 規則 1 && 第一個字串出現的英文字母頻率都必須小於等於第三個字串中出現的。
  5. 規則 1 && 第一個字串可以由第三個字串移除某些位置的字元構成。
  6. 規則 1 && 第一字串長度加上輸入的整數等於第二字串長度。
  7. 規則 1 && 整數必須小於第一字串長度。

Sample Input

1
2
3
4
5
6
abcd 3 abcdcba
aaaa 3 abcdcba
abc 2 abdcba
aab b baab
abababaabababa 0 abababaabababa
pqrsabcdpqrs 9 pqrsabcdpqrqpdcbasrqp

Sample Output

1
2
3
4
5
6
TTTTTTT The solution is accepted
TTTFFTT The solution is not accepted
TFTTTFT The solution is not accepted
FFFFFFF The solution is not accepted
TTTTTTT The solution is accepted
TTTTTTT The solution is accepted

Solution

附上討論區的噁心測資

1
2
3
4
5
6
7
8
9
10
abcd 3 abcdcba
aaaa 3 abcdcba
abc 2 abdcba
aab b baab
abababaabababa 0 abababaabababa
pqrsabcdpqrs 9 pqrsabcdpqrqpdcbasrqp
a 0 aa
aa 0 aa
 0
 2 aa

很明顯地方發現，居然有空字串 …，用空白切割檢查一下參數個數是否正確。

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
#include <stdio.h> 
#include <algorithm>
#include <string.h>
#include <iostream>
#include <sstream>
#include <ctype.h>
using namespace std;
int isValidString(string s, int limit) {
    int ok = 1;
    for (int i = 0; i < s.length(); i++)
        ok &= 'a' <= s[i] && s[i] <= 'z';
    return ok && s.length() <= limit;
}
int isValidInteger(string s) {
    int ok = 1, num = 0;
    for (int i = 0; i < s.length(); i++) {
        ok &= isdigit(s[i]);
        if (isdigit(s[i])) {
            num = num * 10 + s[i] - '0';
            if (num > 1000)
                return 0;
        }
    }
    return ok;
}
int ispalindrome(string s) {
    for (int i = 0, j = s.length() - 1; i < j; i++, j--)
        if (s[i] != s[j])
            return 0;
    return 1;
}
int allLetterIn(string s1, string s2) {
    int c[128] = {};
    for (int i = 0; i < s1.length(); i++)
        c[s1[i]] = 1;
    for (int i = 0; i < s2.length(); i++)
        c[s2[i]] = 0;
    for (int i = 0; i < 128; i++)
        if (c[i] > 0)
            return 0;
    return 1;
}
int checkfrequency(string s1, string s2) {
    int c[128] = {};
    for (int i = 0; i < s1.length(); i++)
        c[s1[i]]++;
    for (int i = 0; i < s2.length(); i++)
        c[s2[i]]--;
    for (int i = 0; i < 128; i++)
        if (c[i] > 0)
            return 0;
    return 1;
}
int checkBuild(string s1, string s2) {
    int idx = 0;
    for (int i = 0; i < s2.length() && idx < s1.length(); i++) {
        if (s1[idx] == s2[i])
            idx++;
    }
    return idx == s1.length();
}
int checkCond6(string s1, string s2, string s3) {
    stringstream sin(s2);
    int n;
    sin >> n;
    return s1.length() + n == s3.length();
}
int checkCond7(string s1, string s2) {
    stringstream sin(s2);
    int n;
    sin >> n;
    return s1.length() > n;
}
int main() {
    string s1, s2, s3;
    char line[32767];
    while (gets(line)) {
        s1 = s2 = s3 = "";
        int n = 0;
        for (int i = 0; line[i]; i++) {
            if (line[i] == ' ')
                n++;
            else {
                if (n == 0)	s1 += line[i];
                if (n == 1)	s2 += line[i];
                if (n == 2)	s3 += line[i];
            }
        }
        if (n != 2) {
            puts("FFFFFFF The solution is not accepted");
            continue;
        }
        int P[10];
        P[0] = isValidString(s1, 1000) && isValidString(s3, 2000) && isValidInteger(s2);
        P[1] = P[0] && ispalindrome(s3);
        P[2] = P[0] && allLetterIn(s1, s3);
        P[3] = P[0] && checkfrequency(s1, s3);
        P[4] = P[0] && checkBuild(s1, s3);
        P[5] = P[0] && checkCond6(s1, s2, s3);
        P[6] = P[0] && checkCond7(s1, s2);
        int ok = 1;
        for (int i = 0; i < 7; i++) {
            printf("%c", P[i] ? 'T' : 'F');
            ok &= P[i];
        }
        printf(" The solution is %saccepted\n", ok ? "" : "not ");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 1641 - ASCII Area

Problem

給一個用 ASCII Area 拉出來的簡單多邊形，求其面積為何？

Sample Input

1
2
3
4
5
4 4
/\/\
\../
.\.\
..\/

Sample Output

1
8

Solution

看別人的代碼相當簡單，只是有點不知道它們怎麼構思的。

首先，保證每一個端點都是格子點，靈機一動想到 Pick’s theorem,$A = i + b/2 - 1$，那麼接著就是找到 i 的個數 (內部存在的整數節點個數)，b 個數 (邊上的整數節點個數)。

b 很好求得，相當於 \ 和 / 的個數而已，然而 i 求法會比較特別一點，思路類似於掃描線的方式，性質則是利用射線法 (一個點拉一個射線無限延伸，如果該點在簡單多邊形內，則會穿過奇數個點。)。

如果是凸多邊形，也許就能用行列式求值。

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
#include <stdio.h> 
// Pick's theorem, A = i + b/2 - 1
int main() {
    char g[128][128];
    int n, m;
    while (scanf("%d %d", &n, &m) == 2) {
        for (int i = 0; i < n; i++)
            scanf("%s", g[i]);
        int B = 0, I = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (g[i][j] == '/' || g[i][j] == '\\')
                    B++;
            }
        }
        
        for (int i = 0; i <= n; i++) {
            int in = 0;
            for (int j = 0; j <= m; j++) {
                int f = 0;
                if (i-1 >= 0 && g[i-1][j] == '/' && g[i][j] == '\\')
                    in++;
                if (i-1 >= 0 && j-1 >= 0 && g[i-1][j-1] == '\\' && g[i][j-1] == '/')
                    in++;
                if (i-1 >= 0 && j-1 >= 0 && g[i-1][j-1] == '\\' && g[i][j] == '\\')
                    in++;
                if (i-1 >= 0 && j-1 >= 0 && g[i-1][j] == '/' && g[i][j-1] == '/')
                    in++;
                if (i-1 >=0 && j-1 >= 0 && g[i-1][j-1] == '\\')	f = 1;
                if (i-1 >=0 && g[i-1][j] == '/')				f = 1;
                if (g[i][j] == '\\')							f = 1;
                if (j-1 >= 0 && g[i][j-1] == '/')				f = 1;
                if (!f && in%2 == 1)
                    I ++;
            }
        }
        printf("%d\n", I + B/2 - 1);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 1610 - Party Games

Problem

給定 N 個字串 (N 為偶數)，現在來了一個人，將其命名名字，其名字長度越小越好，同時必須按照字典順序時，必須大於等於前 N/2 個人，大於 N/2 個人。

在相同的最短長度下，輸出一個字典順序最小的。

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
4
FRED
SAM
JOE
MARGARET
2
FRED
FREDDIE
2
JOSEPHINE
JERRY
2
LARHONDA
LARSEN
2
ABA
AC
2
ABCA
AC
2
ABZA
AC
2
ABZCA
AC
0

Sample Output

1
2
3
4
5
6
7
8
K
FRED
JF
LARI
ABA
ABD
ABZA
ABZD

Solution

先對輸入的字串排序，找到相鄰的兩個中位數字串 p, q (p < q)。

接著分開討論。

  1. p.length() < q.length()：要不前綴相同，或者是比 p 大一點，當前綴都相同時跟 p 相同。
  2. p.length() >= q.length()：一樣貪心處理前綴，特別小心 ‘Z’ 的存在，這種情況將會逼不得已將長度增加，而其他狀況只要想辦法增加字典順序的大小即可。
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
#include <stdio.h> 
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int n;
    char s[1024];
    while (scanf("%d", &n) == 1 && n) {
        vector<string> A;
        for (int i = 0; i < n; i++)
            scanf("%s", s), A.push_back(s);
        sort(A.begin(), A.end());
        string p = A[n/2-1], q = A[n/2];
        if (p.length() < q.length()) {
            for (int i = 0; i < p.length(); i++) {
                if (p[i] == q[i] || i == p.length() - 1) // equal.
                    putchar(p[i]);
                else { // less
                    putchar(p[i] + 1);
                    break;
                }
            }
        } else {
            for (int i = 0; i < q.length(); i++) {
                if (p[i] == q[i])
                    putchar(p[i]);
                else {
                    if (i == q.length() - 1) {
                        if (i == p.length() - 1) { // equal
                            putchar(p[i]);
                            break;
                        }
                        if (p[i] + 1 != q[i]) {
                            putchar(p[i] + 1);
                            break;
                        } else {
                            putchar(p[i]);
                            for (int j = i+1; j < p.length(); j++) {
                                if (j == p.length() - 1) // equal
                                    putchar(p[j]);
                                else if (p[j] != 'Z') {
                                    putchar(p[j] + 1);
                                    break;
                                } else
                                    putchar(p[j]);
                            }
                            break;
                        }
                    } else {
                        putchar(p[i] + 1);
                        break;
                    }
                }
            }
        }
        puts("");
    } 
    return 0;
}
/*
4
FRED
SAM
JOE
MARGARET
2
FRED
FREDDIE
2
JOSEPHINE
JERRY
2
LARHONDA
LARSEN
2
ABA
AC
2
ABCA
AC
2
ABZA
AC
2
ABZCA
AC
0
*/
Read More +
解題區/解題區 - UVa

UVa 1605 - Building for UN

Problem

現在有 N 個國家在一棟建築物裡面各自擁有辦公室，辦公室相鄰的定義為同一樓層的前後左右，或者是上一樓層的同一位置、下一樓層的同一位置。

由於各方想要藉由一面牆或者是天花板進行秘密會議。因此希望每一個國家的辦公室可以跟其他所有辦公室相鄰。

輸出其中一組解即可。

Sample Input

1
2
4
8

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
2 2 2 
AB 
CC 
 
zz 
zz
 
2 8 8
aaaaaaaa
bbbbbbbb
cccccccc
dddddddd
eeeeeeee
ffffffff
gggggggg
hhhhhhhh
 
abcdefgh
abcdefgh
abcdefgh
abcdefgh
abcdefgh
abcdefgh
abcdefgh
abcdefgh

Solution

直接建造兩層，參照如上圖的建造方式，交錯的形式能保證可以在 O(2 n^2) 個數內完成建築物。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
// ignore Print a blank line between test cases.
int main() {
    int n, cases = 0;
    while (scanf("%d", &n) == 1) {
        printf("%d %d %d\n", 2, n, n);
        for (int i = 0; i < n; i++, puts(""))
            for (int j = 0; j < n; j++)
                putchar(i < 26 ? i + 'a' : i-26 + 'A');
        puts("");
        for (int i = 0; i < n; i++, puts(""))
            for (int j = 0; j < n; j++)
                putchar(j < 26 ? j + 'a' : j-26 + 'A');
        puts("");
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 1600 - Patrol Robot

Problem

機器人能轉移只有上下左右四個方向，機器人切換快速移動模式，將自己跨過小於等於 K 個連續的障礙物。也就是說，當障礙物連續出現形成一座厚牆時，機器人就爬不過去。

求最少移動次數。

Sample Input

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

Sample Output

1
2
3
7 
10 
-1

Solution

將每一點多一個狀態 s，表示當前經過連續 s 個障礙物。如果下一個轉移地點不是障礙物，則 s 會歸零。

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
#include <stdio.h> 
#include <string.h>
#include <queue>
using namespace std;
int g[32][32];
int dist[32][32][32];
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
int main() {
    int testcase;
    int N, M, K;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d %d", &N, &M, &K);
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                scanf("%d", &g[i][j]);
        memset(dist, 63, sizeof(dist));
        dist[0][0][0] = 0;
        queue<int> X, Y, S;
        int x, y, s, tx, ty, ts;
        X.push(0), Y.push(0), S.push(0);
        while (!X.empty()) {
            x = X.front(), X.pop();
            y = Y.front(), Y.pop();
            s = S.front(), S.pop();
            for (int i = 0; i < 4; i++) {
                tx = x + dx[i], ty = y + dy[i];
                if (tx < 0 || ty < 0 || tx >= N || ty >= M)
                    continue;
                if (g[tx][ty])
                    ts = s + 1;
                else
                    ts = 0;
                if (ts > K)	continue;
                if (dist[tx][ty][ts] > dist[x][y][s] + 1) {
                    dist[tx][ty][ts] = dist[x][y][s] + 1;
                    X.push(tx), Y.push(ty), S.push(ts);
                }
            }
        }
        int ret = 0x3f3f3f3f;
        for (int i = 0; i <= K; i++)
            ret = min(ret, dist[N-1][M-1][i]);
        printf("%d\n", ret == 0x3f3f3f3f ? -1 : ret);
    }
    return 0;
}
/*
3 
2 5 
0 
0 1 0 0 0 
0 0 0 1 0 
4 6 
1 
0 1 1 0 0 0
0 0 1 0 1 1
0 1 1 1 1 0
0 1 1 1 0 0
2 2 
0 
0 1 
1 0
*/
Read More +
解題區/解題區 - UVa

UVa 1579 - Matryoshka

Problem

俄羅斯套娃遊戲，每一次只能將相鄰的兩個套娃合併。合併時，打開套娃的次數相當於操作成本，請問至少要打開的次數為何，使得最後的數個套娃可以收成連續大小 1 ~ n。

一開始給定每個套娃內部都沒有別的套娃。

從第二組測資中，可以看出必須整理成 [1 2 3][1 2 3 4] 兩組完整的套娃。要把 [2][4] 合併成 [2 4] 要打開大小為 4 的套娃，並且把大小為 2 的套娃裝進去。同理，[1][3] 合併成 [1 3] 也需要打開一次。最後合併 [2 4][1 3] 成 [1 2 3 4] 其中必須將 4 打開 (看到 2)，再把 2 打開，把 3 打開，接著把 1 裝進 2，把 2 裝進 3，最後裝進 4 中。

此時已經花費成本 5 次 (打開次數)，而要把 [1][2][3] 合併成 [1 2 3] 需要打開 2、打開 3 才能完成。共計成本 7 次。

Sample Input

1
2
3
4
7
1 2 1 2 4 3 3
7
1 2 3 2 4 1 3

Sample Output

1
2
impossible
7

Solution

類似矩陣鏈乘積 DP，但是這一題必須使用兩次 DP。

  1. 第一次計算 dp[l, r] 找到序列 [l, r] 之間合併成一個套娃的花費。－O(n^3)
  2. 之後檢查 A[l, r] 之間是否是一個 complete set，也就是一個完整的套娃 (連續大小)。－O(n^3) 這裡應該還可以更快，不過步驟 1 應該很慢，所以沒有必要。
  3. 最後，組合數個連續區段套娃，進行區間合併的操作。－O(n^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
#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
#define MAXN 512
int A[MAXN];
int dp[MAXN][MAXN] = {}, complete[MAXN][MAXN];
int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i < n; i++)
            scanf("%d", &A[i]);
        
        for (int i = 1; i < n; i++) { // build cost table.
            for (int j = 0; i + j < n; j++) {
                int l = j, r = i + j;
                int &val = dp[l][r];
                val = 0x3f3f3f3f;
                for (int k = l; k < r; k++) {
                    int open = 0; // [l, r] = L[l, k] + R[k+1, r]
                    int minL = 0x3f3f3f3f, minR = 0x3f3f3f3f;
                    for (int p = l; p <= k; p++)
                        minL = min(minL, A[p]);
                    for (int p = k+1; p <= r; p++)
                        minR = min(minR, A[p]);
                    for (int p = l; p <= k; p++)
                        open += A[p] > minR;
                    for (int p = k+1; p <= r; p++)
                        open += A[p] > minL;
//					printf("[%d %d %d %d] %d %d\n", l, k, k+1, r, dp[l][k] + dp[k+1][r]+ open, open);
                    val = min(val, dp[l][k] + dp[k + 1][r] + open); 
                }
            }
        }
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; i + j < n; j++) {
                int l = j, r = i + j, m = i + 1; // [l, r] need 1, 2, 3, ..., m
                int used[MAXN] = {}, ok = 1;
                for (int k = l; k <= r && ok; k++) {
                    if (A[k] > m) {
                        ok = 0;
                        break;
                    }
                    used[A[k]]++;
                    if (used[A[k]] > 1)	ok = 0;
                }
                complete[l][r] = ok;
            }
        }
        
        int dp2[MAXN];
        for (int i = 0; i <= n; i++)
            dp2[i] = 0x3f3f3f3f;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (complete[i][j]) {
                    int comb = dp[i][j];
                    if (i)	comb += dp2[i-1];
                    dp2[j] = min(dp2[j], comb);
                }
            }
        }
        if (dp2[n - 1] == 0x3f3f3f3f)
            puts("impossible");
        else
            printf("%d\n", dp2[n - 1]);
    }
    return 0;
}
/*
7
1 2 1 2 4 3 3
7
1 2 3 2 4 1 3
2
1 1
2 
2 1
5
1 3 2 3 1
5
1 2 2 3 1
*/
Read More +
解題區/解題區 - UVa

UVa 10117 - Nice Milk

Problem

有一個凸多邊形的餅乾要沾牛奶，但是杯子的深度有限，最多沾 h 高，而最多拿 k 個邊去沾，請問最多沾到的面積為何？

Sample Input

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

Sample Output

1
7.46

Solution

最多只有 20 條邊，因此窮舉 C(20, k) 然後計算沒沾到沾到的最小面積為何。藉此得到最大沾有面積為多少。

沾到的面積計算採用半平面交的方式。如果使用該邊去沾牛奶，則將此邊往內推根據法向量內推 h 距離。

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
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
#define eps 1e-10
#define MAXN 131072
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 {
        if (fabs(x - a.x) > eps)
            return x < a.x;
        if (fabs(y - a.y) > eps)
            return y < a.y;
        return false;
    }
};
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;
    }
};
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;
}
Seg deq[MAXN];
vector<Pt> halfPlaneIntersect(vector<Seg> segs) {
    sort(segs.begin(), segs.end());
    int n = segs.size(), m = 1;
    int front = 0, rear = -1;
    for (int i = 1; i < n; i++) {
        if (fabs(segs[i].angle - segs[m-1].angle) > eps)
            segs[m++] = segs[i];
    }
    n = m;
    deq[++rear] = segs[0];
    deq[++rear] = segs[1];
    for (int i = 2; i < n; i++) {
        while (front < rear && cross(segs[i].s, segs[i].e, getIntersect(deq[rear], deq[rear-1])) < eps)
            rear--;
        while (front < rear && cross(segs[i].s, segs[i].e, getIntersect(deq[front], deq[front+1])) < eps)
            front++;
        deq[++rear] = segs[i];
    }
    while (front < rear && cross(deq[front].s, deq[front].e, getIntersect(deq[rear], deq[rear-1])) < eps)
        rear--;  
    while (front < rear && cross(deq[rear].s, deq[rear].e, getIntersect(deq[front], deq[front+1])) < eps)
    	front++;
    vector<Pt> ret;
    for (int i = front; i < rear; i++) {
        Pt p = getIntersect(deq[i], deq[i+1]);
        ret.push_back(p);
    }
    if (rear > front + 1) {
        Pt p = getIntersect(deq[front], deq[rear]);
        ret.push_back(p);
    } 
    return ret;
}
double calcArea(vector<Pt> p) {
    double ret = 0;
    int n = p.size();
    if(n < 3) return 0.0;
    for(int i = 0, j = n-1; i < n; j = i++)
        ret += p[i].x * p[j].y - p[i].y * p[j].x;
    return fabs(ret)/2;
}
Pt D[32];
int main() {
    int n, m;
    double h;
    while (scanf("%d %d %lf", &n, &m, &h) == 3 && n) {
        vector<Pt> O;
        Seg Oe[32];
        for (int i = 0; i < n; i++) {
            scanf("%lf %lf", &D[i].x, &D[i].y);
            O.push_back(D[i]);
        }
        D[n] = D[0], O.push_back(D[0]);
        for (int i = 0; i < n; i++) {
            Pt a = D[i], b = D[i+1]; // \vec{ab}
            Pt nab(b.y - a.y, a.x - b.x); // normal vector
            double v = hypot(nab.x, nab.y);
            nab.x = nab.x / v * h, nab.y = nab.y / v * h;
            a = a - nab, b = b - nab;
            Oe[i] = Seg(a, b);
        }
        int A[32] = {};
        for (int i = 0; i < m; i++)
            A[i] = 1;
        sort(A, A+n);
        double area = calcArea(O), ret = 0;
        do {
            vector<Seg> segs;
            for (int i = 0; i < n; i++)
                if (A[i])
                    segs.push_back(Oe[i]);
                else
                    segs.push_back(Seg(O[i], O[i+1]));
            vector<Pt> convex = halfPlaneIntersect(segs);
            double d = calcArea(convex);
            ret = max(ret, area - d);
        } while (next_permutation(A, A+n));
        printf("%.2lf\n", ret);
    }
    return 0;
}
/*
4 2 1
1 0
3 0
5 2
0 4
4 1 1
1 0
3 0
5 2
0 4
0 0 0
*/
Read More +
解題區/解題區 - UVa

UVa 1475 - Jungle Outpost

Problem

有一個軍事基地在叢林深處隱藏，基地將會由 n 個塔台包圍保護。並且只能保護其凸包內的所有地區。

敵人可以摧毀一些塔，使得保護區的保護範圍縮小，使得基地給暴露出來。

在萬無一失的條件下，希望將基地建造在敵人需要摧毀最多塔台才能基地所在地。

Sample Input

1
2
3
4
5
6
7
8
9
10
3 
0 0 
50 50 
60 10 
5 
0 0 
0 10 
10 20 
20 10 
25 0

Sample Output

1
2
1
2

Solution

二分需要摧毀的塔台數 K，由於敵人最多摧毀 K 個塔台，就能將基地給找出來，也就是說任意炸掉連續區段的塔台，他們所產生出來的交集是存在的。如果沒有存在交集，則基地可以藏在那裏面，不管敵人怎麼摧毀都找不到基地在哪。

為什麼需要連續呢？分段結果肯定不好，涵蓋的面積也少，同時會被連續 K 的情況給包含，所以不用考慮分段。

N 很大，半平面交的誤差也很大。

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
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
#define eps 1e-9
#define MAXN 131072
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 {
        if (fabs(x - a.x) > eps)
            return x < a.x;
        if (fabs(y - a.y) > eps)
            return y < a.y;
        return false;
    }
};
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;
    }
};
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;
}
Seg deq[MAXN];
int halfPlaneIntersect(vector<Seg> segs) {
    sort(segs.begin(), segs.end());
    int n = segs.size(), m = 1;
    int front = 0, rear = -1;
    for (int i = 1; i < n; i++) {
        if (fabs(segs[i].angle - segs[m-1].angle) > eps)
            segs[m++] = segs[i];
    }
    n = m;
    deq[++rear] = segs[0];
    deq[++rear] = segs[1];
    for (int i = 2; i < n; i++) {
        while (front < rear && cross(segs[i].s, segs[i].e, getIntersect(deq[rear], deq[rear-1])) < eps)
            rear--;
        while (front < rear && cross(segs[i].s, segs[i].e, getIntersect(deq[front], deq[front+1])) < eps)
            front++;
        deq[++rear] = segs[i];
    }
    while (front < rear && cross(deq[front].s, deq[front].e, getIntersect(deq[rear], deq[rear-1])) < eps)
        rear--;  
    while (front < rear && cross(deq[rear].s, deq[rear].e, getIntersect(deq[front], deq[front+1])) < eps)
    	front++;
    return front + 1 < rear;
//    vector<Pt> ret;
//	for (int i = front; i < rear; i++) {
//		Pt p = getIntersect(deq[i], deq[i+1]);
//		ret.push_back(p);
//	}
//	if (rear > front + 1) {
//		Pt p = getIntersect(deq[front], deq[rear]);
//		ret.push_back(p);
//	} 
//	return ret;
}
int testBlowUp(int m, Pt D[], int n) {
    vector<Seg> segs;
    for (int i = 0; i < n; i++) {
        Pt a = D[i], b = D[i + m];
        segs.push_back(Seg(b, a));
    }
    return halfPlaneIntersect(segs);
}
Pt D[131072];
int main() {
    int n;
    while (scanf("%d", &n) == 1 && n) {
        for (int i = 0; i < n; i++) {
            scanf("%lf %lf", &D[i].x, &D[i].y);
            D[i + n] = D[i];
        }
        if (n <= 3) {
            puts("1");
            continue;
        }
        int l = 1, r = n - 2, mid, ret;
        while (l <= r) {
            mid = (l + r)/2;
            if(testBlowUp(mid, D, n))
                l = mid + 1, ret = mid;
            else
                r = mid - 1;
        }
        printf("%d\n", ret);
    }
    return 0;
}
/*
3 
0 0 
50 50 
60 10 
5 
0 0 
0 10 
10 20 
20 10 
25 0
*/
Read More +
解題區/解題區 - UVa

UVa 1396 - Most Distant Point from the Sea

Problem

給一個逆時針順序的凸多邊形，找一個內接最大圓。求出最大半徑為何。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
4 
0 0 
10000 0 
10000 10000 
0 10000 
3 
0 0 
10000 0 
7000 1000 
6 
0 40 
100 20 
250 40 
250 70 
100 90 
0 70 
3 
0 0 
10000 10000 
5000 5001 
0

Sample Output

1
2
3
4
5000.000000 
494.233641 
34.542948 
0.353553

Solution

二分半徑 r，如果內側放置一個圓，則保證每一條邊到圓心距離都大於等於 r。

藉此嘗試將每一條邊往內推，計算半平面交集是否存在，往內推根據法向量內推 r 距離。

求半平面交需要 O(n log n)，二分又有一個 log k，所以效率必須是 O(n log n log k)。

關於是否需要半平面交還有一個擴充，由於這題不求半平面結果，單純詢問有交集與否，可以利用 2D randomized bounded LP，隨機順序放置半平面，維護最下方的最佳解，如果不存在就 O(n) 建立 (不存在的機率 1/i，因此 O(n)/n = O(1))，可以在 O(n) 完成，這麼一來速度也許還能再更快些。有空再來實作。

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
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
#define eps 1e-7
#define MAXN 32767
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);
    }
    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 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);
}
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;
    }
};
Pt getIntersect(Seg a, Seg b) {
    double a1, b1, c1, a2, b2, c2;
    double dx, dy, d;
    a1 = a.s.y - a.e.y, b1 = a.e.x - a.s.x;
    c1 = a1 * a.s.x + b1 * a.s.y;
    a2 = b.s.y - b.e.y, b2 = b.e.x - b.s.x;
    c2 = a2 * b.s.x + b2 * b.s.y;
    dx = c1 * b2 - c2 * b1, dy = a1 * c2 - a2 * c1;
    d = a1 * b2 - a2 * b1;
    return Pt(dx/d, dy/d);
}
Seg deq[MAXN];
int halfPlaneIntersect(vector<Seg> segs) {
    sort(segs.begin(), segs.end());
    int n = segs.size(), m = 1;
    int front = 0, rear = -1;
    for (int i = 1; i < n; i++) {
        if (fabs(segs[i].angle - segs[m-1].angle) > eps)
            segs[m++] = segs[i];
    }
    n = m;
    deq[++rear] = segs[0];
    deq[++rear] = segs[1];
    for (int i = 2; i < n; i++) {
        while (front < rear && cross(segs[i].s, segs[i].e, getIntersect(deq[rear], deq[rear-1])) < -eps)
            rear--;
        while (front < rear && cross(segs[i].s, segs[i].e, getIntersect(deq[front], deq[front+1])) < -eps)
            front++;
        deq[++rear] = segs[i];
    }
    while (front < rear && cross(deq[front].s, deq[front].e, getIntersect(deq[rear], deq[rear-1])) < -eps)
        rear--;  
    while (front < rear && cross(deq[rear].s, deq[rear].e, getIntersect(deq[front], deq[front+1])) < -eps)
    	front++;
    return front + 1 < rear;
//    vector<Pt> ret;
//	for (int i = front; i < rear; i++) {
//		Pt p = getIntersect(deq[i], deq[i+1]);
//		ret.push_back(p);
//	}
//	if (rear > front + 1) {
//		Pt p = getIntersect(deq[front], deq[rear]);
//		ret.push_back(p);
//	} 
//	return ret;
}
int testRadius(double r, Pt D[], int n) {
    vector<Seg> segs;
    for (int i = 0, j = n-1; i < n; j = i++) {
        Pt a = D[j], b = D[i]; // \vec{ab}
        Pt nab(b.y - a.y, a.x - b.x); // normal vector
        double v = hypot(nab.x, nab.y);
        nab.x = nab.x / v * r, nab.y = nab.y / v * r;
        a = a - nab, b = b - nab;
        segs.push_back(Seg(a, b));
    }
    return halfPlaneIntersect(segs);
}
int main() {
    int n;
    Pt D[128];
    while (scanf("%d", &n) == 1 && n) {
        for (int i = 0; i < n; i++)
            scanf("%lf %lf", &D[i].x, &D[i].y);
        double l = 0, r = 10000, mid, ret;
        while (fabs(l - r) > eps) {
            mid = (l + r)/2;
            if(testRadius(mid, D, n))
                l = mid, ret = mid;
            else
                r = mid;
        }
        printf("%lf\n", ret);
    }
    return 0;
}
/*
4 
0 0 
10000 0 
10000 10000 
0 10000 
3 
0 0 
10000 0 
7000 1000 
6 
0 40 
100 20 
250 40 
250 70 
100 90 
0 70 
3 
0 0 
10000 10000 
5000 5001 
0
*/
Read More +
解題區/解題區 - UVa

UVa 12587 - Reduce the Maintenance Cost

Problem

在 N 個城市，每個城市都要每月的基礎花費，而在城市之間有 M 條邊，市長安排在邊兩側的城市其一要負責維護這一條重要邊，而重要邊的維護花費為該邊移除後，導致任兩個城市之間無法相連的對數乘上該路長。

只需要將一條邊交給相鄰的其一城市維護即可，因此會將該城市的月花費上升，求一種分配方案使得城市的最大花費最小。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
3
2 1
5 10
1 2 10
  
6 6
10 20 30 40 50 60
1 2 1
2 3 1
1 3 1
1 4 6
1 5 6
4 6 2
  
3 1
10 20 30
2 3 1

Sample Output

1
2
3
Case 1: 15
Case 2: 80
Case 3: 30

Solution

首先，重要邊只有 bridge 需要維護，除了 bridge 外，不會造成任兩個點之間不連通的情況。

因此將所有 bridge 求出，建造出森林 (很多棵 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
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
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
struct edge {
    int x, y, s;
    long long w;
    edge(int a=0, int b=0, long long c=0, int d=0):
        x(a), y(b), w(c), s(d) {}
};
vector<edge> g[32767];
int visited[32767], depth[32767], back[32767];
vector<edge> bridge;
int findBridge(int u, int p, int dep) {
    visited[u] = 1, depth[u] = dep;
    back[u] = 0x3f3f3f3f;
    int sz = 1, t;
    for(int i = 0; i < g[u].size(); i++) {
        int v = g[u][i].y;
        if(v == p)	continue;
        if(!visited[v]) {
            t = findBridge(v, u, dep+1);
            sz += t;
            if(back[v] > dep)
                bridge.push_back(edge(u, v, g[u][i].w, t));
            back[u] = min(back[u], back[v]);
        } else {
            back[u] = min(back[u], depth[v]);
        }
    }
    return sz;
}
vector<edge> tree[32767];	
long long node_w[32767], place_w[32767];
int dfs(int u, long long mx_w, int p, long long p_w) {
    visited[u] = 1;
    for (int i = 0; i < tree[u].size(); i++) {
        int v = tree[u][i].y;
        if (visited[v] == 0) {
            if (!dfs(v, mx_w, u, tree[u][i].w))
                return 0;
        }
    }
    if (place_w[u] + p_w <= mx_w)
        place_w[u] += p_w;
    else
        place_w[p] += p_w;
    if (place_w[u] > mx_w)
        return 0;
    return 1;
        
}
int check(long long mx_w, int n) {
    for (int i = 1; i <= n; i++)
        visited[i] = 0, place_w[i] = node_w[i];
    int ok = 1;
    for (int i = 1; i <= n && ok; i++) {
        if (visited[i] == 0) {
            ok &= dfs(i, mx_w, 0, 0);
        }
    }
//	printf("check %d ok %d\n", mx_w, ok);
    return ok;
}
int main() {
    int testcase, cases = 0, n, m, x, y, w;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        
        long long sum = 0, low_w = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%lld", &node_w[i]);
            g[i].clear(), tree[i].clear();
            sum += node_w[i], low_w = max(low_w, node_w[i]);
        }
        
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d", &x, &y, &w);
            g[x].push_back(edge(x, y, w));
            g[y].push_back(edge(y, x, w));
        }
        
        memset(visited, 0, sizeof(visited));
        for (int i = 1; i <= n; i++) {
            if (visited[i] == 0) {
                bridge.clear();
                int comp_size = findBridge(i, -1, 0);
                for (int j = 0; j < bridge.size(); j++) {
                    long long N = (long long) bridge[j].s * (comp_size - bridge[j].s);
                    tree[bridge[j].x].push_back(edge(bridge[j].x, bridge[j].y, bridge[j].w * N));
                    tree[bridge[j].y].push_back(edge(bridge[j].y, bridge[j].x, bridge[j].w * N));
                    sum += bridge[j].w * N;
//					printf("%d %d - %d\n", bridge[j].x, bridge[j].y, bridge[j].w * N);
                }
            }
        }
        
        // binary search answer
        long long l = low_w, r = sum, mid, ret;
        while (l <= r) {
            mid = (l + r)/2;
            if (check(mid, n))
                r = mid - 1, ret = mid;
            else
                l = mid + 1;
        }
        printf("Case %d: %lld\n", ++cases, ret);
    }
    return 0;
}
/*
3
2 1
5 10
1 2 10
6 6
10 20 30 40 50 60
1 2 1
2 3 1
1 3 1
1 4 6
1 5 6
4 6 2
3 1
10 20 30
2 3 1
9999
3 3
4 5 6
1 2 1
2 3 1
3 1 1
*/
Read More +