解題區/出題解題

[ACM 題目] 順來逆受

Problem

「其實雙親不准我在家裡畫漫畫。」
「是嗎？你都畫些什麼啊」
「乃是在下 x 大哥的原創本是也。」
「還有，薰是普通人」
「薰姐，功的反義詞是什麼？」
「什麼？是守嗎？」
「薰姐，剛才我說的話請你全忘記吧。」

在一個 N 個城市的國家，每個城市之間用 M 條邊相連。隨著時間，它們開始分裂，彼此會開始斷訊，無法聯絡到相鄰的城市。定時回報某個城市可以藉由間接或直接連絡的城市個數。

操作：

  • D i：移除輸入順序 i 個連接邊。
  • Q i：輸出城市 i 能聯絡的城市個數。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
5 5
1 2
1 3
2 3
3 4
4 5
4
Q 1
D 4
Q 5
Q 2

Sample Output

1
2
3
5
2
3

Solution

1
Read More +
解題區/出題解題

[ACM 題目] 動態前綴

Problem

某 M 「給一個字串 S，接著詢問操作 [l, r] 告訴區間內是否剛好為一個迴文？」
學弟 「用最長迴文的方式去想嗎？」
某 M 「我沒有標準答案哦 wwww，吾等還在想能不能離線 O(1)。」

暗自敲著 UVa 另外一題類似題說著，就算能 O(1) 檢查迴文，區間還是要窮舉 O(n)，在此宣告某 M 陣亡－ Time Limit 。

某 M 心想，假解也是不錯選擇，單純詢問迴文肯定會被 manacher’s algorithm 秒掉 (O(1) - O(n))。如果詢問 [l, r] 的子字串是否符合 pattern AA (例如 abcabc，其中 A = abc)，也會被 suffix array、suffix tree 解決 (O(log n) - O(n log n)/O(n))。

百般無奈之下，也許這題就這樣定好了：

C p x：將字串位置 p 修改成字符 x。
Q p q：求子字串 S.substr(p) 和 S.substr(q) 的最長共同前綴長度。

1
2
3
4
5
6
7
8
void change(char s[], int p, int x) {
    s[p] = x;
}
int query(char s[], int p, int q) {
    int ret = 0;
    for (; s[p] == s[q] && s[p] && s[q]; p++, q++, ret++);
    return ret;
}

Sample Input

1
2
3
4
5
abcdabcc
3
Q 0 4
C 3 c
Q 0 4

Sample Output

1
2
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
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 <string.h>
#include <algorithm>
#include <assert.h>
using namespace std;
const long long mod = 100000007LL;
#define MAXN (1<<17)
char S[MAXN];
long long base[MAXN];
long long tree[MAXN<<1];
long long build(int k, int l, int r) {
    assert(l <= r);
    if (l == r)
        return tree[k] = (S[l] % mod);
    int m = (l + r)/2;
    build(k<<1, l, m);
    build(k<<1|1, m+1, r);
    tree[k] = (tree[k<<1] * base[r - m] + tree[k<<1|1]) %mod;
}
void modify(int k, int l, int r, int x, int v) {
    if (l == r) {
        tree[k] = v;
        return;
    }
    int m = (l + r)/2;
    if (x <= m)
        modify(k<<1, l, m, x, v);
    else
        modify(k<<1|1, m+1, r, x, v);
    tree[k] = (tree[k<<1] * base[r - m]%mod + tree[k<<1|1]) %mod;
}
long long query(int k, int l, int r, int x, int y) {
    assert(l >= 0 && l <= r);
    if (x <= l && r <= y) {
        return tree[k];
    }
    int m = (l + r)/2;
    if (y <= m)
        return query(k<<1, l, m, x, y);
    else if(x > m)
        return query(k<<1|1, m+1, r, x, y);
    else {
        long long p, q;
        p = query(k<<1, l, m, x, y);
        q = query(k<<1|1, m+1, r, x, y);
        return (p * base[min(y, r) - m]%mod + q) %mod;
    }
}
int main() {
    freopen("in.txt", "r+t", stdin);
    freopen("out.txt", "w+t", stdout); 
    base[0] = 1;
    for (int i = 1; i < MAXN; i++) 
        base[i] = (base[i-1] * 2)%mod;
    char cmd[8], s[8];
    int Q, p, q, n;
    while (scanf("%s", S) == 1) {
        n = strlen(S);
        build(1, 0, n - 1);
        scanf("%d", &Q);
        for (int i = 0; i < Q; i++) {
            scanf("%s", cmd);
            if (cmd[0] == 'Q') {
                scanf("%d %d", &p, &q);
                if (p == q) {
                    printf("%d\n", n - p);
                    continue;
                } else if (S[p] != S[q]) {
                    puts("0");
                    continue;
                }
                int l = 0, r = min(n - p, n - q) - 1, m, ret = 0;
                long long hp, hq;
                while (l <= r) {
                    m = (l + r)/2;
                    hp = query(1, 0, n-1, p, p + m);
                    hq = query(1, 0, n-1, q, q + m);
                    if (hp == hq)
                        l = m + 1, ret = m;
                    else
                        r = m - 1;
                }
                printf("%d\n", ret + 1);
            } else {
                scanf("%d %s", &p, s);
                S[p] = s[0];
                modify(1, 0, n - 1, p, s[0]);
            }
        }
    }
    return 0;
}
Read More +
解題區/出題解題

[ACM 題目] 最近餐館

Problem

每到吃飼料時間，某 M 正思考要去哪裡解決，雖然有很多很多地方可以去吃，由於某 M 對於美食沒有特別需求，所以只會到最近的幾個地點即可，然後再以循環輪食的方式日復一日。

某 M 現在的位置與每個餐館的位置都用一個笛卡爾坐標系中的點表示，每個點與每個點的距離為歐幾里得距離。

x = (x1,…,xn) 和 y = (y1,…,yn) 之間的距離為

test

現給出在 K 維空間中某 M 所處的位置座標，以及 N 個餐館位置，請觀察某 M 會到哪裡吃飼料。.

Input

輸入有多組測資，

每一組第一行會有兩個整數 N, K，

接下來會有 N 行，每行包含 K 個整數，表示第 i 個餐館座標。

接下來一行，包含一個整數 Q，表示某 M 的可能座標 。

接下來會有 Q 行，每一組詢問會有兩行，第一行會有 K 個整數，表示某 M 所在的座標，第二行會有一個整數 P。

(N < 8192, K < 6, Q < 10,000, P < 11, 座標值 0 < x, y < 10,000)

Output

對於每一組詢問，輸出一行 Case #:，第一個整數為 P，接下來 P 個整數按照距離由小到大輸出餐館編號，如果相同則輸出編號小的。

Sample Input

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

Sample Output

1
2
3
Case 1: 1 1
Case 2: 2 2 3
Case 3: 1 2

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
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
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define MAXN 8192
#define MAXD 8
#define INF 0x3f3f3f3f
class kdTree {
    public:	
    struct PointD {
        int d[MAXD];
        int label;
    };
    struct Node {
    	Node *lson, *rson;
    	int label;
    };
    struct cmp {
        bool operator()(const PointD* x, const PointD* y) const {
    		return x->d[sortDidx] < y->d[sortDidx];
        }
    };
    struct pQcmp {
        bool operator() (pair<int, int> &a, pair<int, int> &b) const {
        	if (a.first != b.first)	return a.first < b.first;
        	return a.second < b.second;
        }
    };
    static int sortDidx;
    priority_queue<pair<int, int>, vector< pair<int, int> >, pQcmp> pQ; // <dist, label>
    Node buf[MAXN], *root;
    PointD pt[MAXN], *A[MAXN];
    int bufsize, K;
    int Q[MAXD], max_dist, qM;
    void prepare(int n) {
        bufsize = 0;
        for (int i = 0; i < n; i++)
        	A[i] = &pt[i];
        root = build(0, 0, n - 1);
    }
    Node* build(int k, int l, int r) {
        if(l > r)	return NULL;
        int m = (l + r)/2;
        Node *ret = &buf[bufsize++];
        sortDidx = k;
        nth_element(A + l, A + m, A + r + 1, cmp());
        ret->label = A[m]->label, ret->lson = ret->rson = NULL;
        if(l != r) {
            ret->lson = build((k+1)%K, l, m-1);
            ret->rson = build((k+1)%K, m+1, r);
        }
        return ret;
    }
    int dist(int idx) {
        int ret = 0;
        for(int i = 0; i < K; i++)
            ret += (pt[idx].d[i] - Q[i]) * (pt[idx].d[i] - Q[i]);
        return ret;
    }
    int h_func(int h[]) {
        int ret = 0;
        for(int i = 0; i < K; i++)	ret += h[i];
        return ret;
    }
    void findNearest(Node *u, int k, int h[]) {
        if(u == NULL || h_func(h) >= max_dist)
            return;
        int d = dist(u->label);
        if (d < max_dist) {
            pQ.push(make_pair(d, u->label));
            if (pQ.size() == qM + 1) {
                max_dist = pQ.top().first, pQ.pop();
            }
        }
        int old_hk = h[k];
        if (Q[k] <= pt[u->label].d[k]) {
            if (u->lson != NULL)
                findNearest(u->lson, (k+1)%K, h);
            if (u->rson != NULL) {
                h[k] = (pt[u->label].d[k] - Q[k]) * (pt[u->label].d[k] - Q[k]);
                findNearest(u->rson, (k+1)%K, h);
                h[k] = old_hk;
            }
        } else {
            if (u->lson != NULL) {
                h[k] = (pt[u->label].d[k] - Q[k]) * (pt[u->label].d[k] - Q[k]);
                findNearest(u->lson, (k+1)%K, h);
                h[k] = old_hk;
            }
            if(u->rson != NULL)
                findNearest(u->rson, (k+1)%K, h);
        }
    }
    void query(int p[], int M) {
        for (int i = 0; i < K; i++)
            Q[i] = p[i];
        max_dist = INF, qM = M;
        int h[MAXD] = {};
        findNearest(root, 0, h);
        printf("%d", M);
        vector<int> ret;
        while (!pQ.empty())
            ret.push_back(pQ.top().second), pQ.pop();
        for (int i = ret.size() - 1; i >= 0; i--)
        	printf(" %d", ret[i] + 1);
        puts("");
    }
};	
int kdTree::sortDidx;
kdTree tree;
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    int n, m, q, p[MAXD], x;
    int cases = 0;
    while (scanf("%d %d", &n, &m) == 2) {
    	tree.K = m;
    	for (int i = 0; i < n; i++) {
    		for (int j = 0; j < m; j++)
    			scanf("%d", &tree.pt[i].d[j]);
    		tree.pt[i].label = i;
    	}
    	tree.prepare(n);
        scanf("%d", &q);
        while (q--) {
        	for (int i = 0; i < m; i++)
        		scanf("%d", &p[i]);
        	scanf("%d", &x);
        	printf("Case %d: ", ++cases);
        	tree.query(p, x);
        }
    }
    return 0;
}
/*
2 2
1 1
3 3
1
2 2
1
3 2
1 1
1 3
3 4
2
2 3
2
2 3
1
*/
Read More +
解題區/出題解題

[ACM 題目] 等高線

Problem

給一個等高線二維地圖，每一個等高線由一個平行兩軸的矩形構成，有 N 個矩形、 M 個地點，輸出每一個地點的所在位置高度，以及當前的所在矩形編號。

保證矩形之間的邊不相交。

exmple 1

Input

有多組測資，

每一組第一行會有一個整數 N，表示接下來有多少個等高線。
接下來會有 N 行，每行上會有四個整數 (lx, ly, rx, ry)。

接著一行一個整數 M，表示接下來有 M 個點詢問，接下來會有 M 行 (x, y)。

N < 32767, 0 < lx < rx < 1,000,000, 0 < ly < ry < 1,000,000

-10,000,000 < x, y < 10,000,000

Output

每組第一行，按照輸入順序輸出每條等高線高度，接著輸出 M 行詢問所在的等高線編號。

Sample Input

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

Sample Output

1
2
3
4
5
6
7
1 2 2 3 3 3 2
3
2
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
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 <set>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
struct Rectangle {
    int lx, ly, rx, ry;
    void read() {
        scanf("%d %d %d %d", &lx, &ly, &rx, &ry);
    }
    int contain(Rectangle &a) {
        return lx <= a.lx && ly <= a.ly && rx >= a.rx && ry >= a.ry;
    }
    int contain(int x, int y) {
        return lx <= x && ly <= y && rx >= x && ry >= y;
    }
} rect[32767];
struct QPt {
    int x, y, label;
    QPt(int a = 0, int b = 0, int c = 0):
        x(a), y(b), label(c) {}
    bool operator<(const QPt &a) const {
        return make_pair(x, y) < make_pair(a.x, a.y);
    }
};
vector<int> g[32767];
int parent[32767], visited[32767], depth[32767];
void dfs(int u) {
    visited[u] = 1;
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (visited[v] == 0) {
            if (rect[u].contain(rect[v]))
                parent[v] = u, depth[v] = depth[u] + 1;
            else
                parent[v] = parent[u], depth[v] = depth[parent[u]] + 1;
            dfs(v);
        }
    }
}
int main() {	
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    int n, m, x, y;
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i < n; i++)
            rect[i].read(), g[i].clear(), visited[i] = 0;
        scanf("%d", &m);
        vector<QPt> XY;
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            XY.push_back(QPt(x, y, i));
        }
        map<int, vector< pair<int, int> > > R;
        for (int i = 0; i < n; i++) {
            vector< pair<int, int> > &l = R[rect[i].lx], &r = R[rect[i].rx];
            l.push_back(make_pair(i, 1));
            l.push_back(make_pair(i, 2));
            r.push_back(make_pair(i, -1));
            r.push_back(make_pair(i, -2));
        }
        set< pair<int, int> > S;
        set< pair<int, int> >::iterator Sit, Sjt;
        for (map<int, vector< pair<int, int> > >::iterator it = R.begin();
            it != R.end(); it++) {
            vector< pair<int, int> > &D = it->second;
            for (int i = 0; i < D.size(); i++) {
                int k = D[i].first;
                if (D[i].second > 0) {
                    if (D[i].second == 1) {
                        Sit = S.lower_bound(make_pair(rect[k].ly, -1)), Sjt = Sit;
                        if (Sit != S.begin()) {
                            Sjt--;
                            g[Sjt->second].push_back(k);
                        }
                        S.insert(make_pair(rect[k].ly, k));
                    } else {
                        Sit = S.lower_bound(make_pair(rect[k].ry, -1)), Sjt = Sit;
                        if (Sit != S.end()) {
                            g[Sit->second].push_back(k);
                        }
                        S.insert(make_pair(rect[k].ry, k));
                    }
                } else {
                    if (D[i].second == -1)	S.erase(make_pair(rect[k].ly, k));
                    else					S.erase(make_pair(rect[k].ry, k));
                }
            }
        }
        int indeg[32767] = {};
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < g[i].size(); j++)
                indeg[g[i][j]]++;
        }
        for (int i = 0; i < n; i++) {
            if (indeg[i] == 0) {
                parent[i] = -1, depth[i] = 1;
                dfs(i);
            }
        }
        for (int i = 0; i < n; i++)
            printf("%d%c", depth[i], i == n - 1 ? '\n' : ' ');
            
        sort(XY.begin(), XY.end());		
        int run_m = 0, OUT[32767] = {};
        S.clear();
        for (map<int, vector< pair<int, int> > >::iterator it = R.begin();
            it != R.end(); it++) {					
            vector< pair<int, int> > &D = it->second;
            for (int i = 0; i < D.size(); i++) {
                int k = D[i].first;
                if (D[i].second > 0) {
                    if (D[i].second == 1) {
                        Sit = S.lower_bound(make_pair(rect[k].ly, -1)), Sjt = Sit;
                        S.insert(make_pair(rect[k].ly, k));
                    } else {
                        Sit = S.lower_bound(make_pair(rect[k].ry, -1)), Sjt = Sit;
                        S.insert(make_pair(rect[k].ry, k));
                    }
                }
            }			
            while (run_m < m && XY[run_m].x <= it->first) {
                Sit = S.lower_bound(make_pair(XY[run_m].y, -1));
                if (rect[Sit->second].contain(XY[run_m].x, XY[run_m].y))
                    OUT[XY[run_m].label] = Sit->second;
                else
                    OUT[XY[run_m].label] = parent[Sit->second];
                run_m++;
            }
            for (int i = 0; i < D.size(); i++) {
                int k = D[i].first;
                if (D[i].second < 0) {
                    if (D[i].second == -1)	S.erase(make_pair(rect[k].ly, k));
                    else					S.erase(make_pair(rect[k].ry, k));
                }
            }
        }
        for (int i = 0; i < m; i++)
            printf("%d\n", OUT[i]);
    }
    return 0;
}
/*
7
0 0 10 10
1 1 9 2
1 3 9 7
2 4 4 6
5 4 6 5
7 5 8 6
1 8 9 9 
6 
3 5
6 6
7 4
9 1 
2 4 
-1 -1 
*/
Read More +
解題區/出題解題

[ACM 題目] 單調測試

Problem

單調－這性質相當巧妙，可以在算法上好好地敲上一筆，處理速度跟你輸入的速度一樣快呢。

Background

這是計算幾何作業中的一環，但是找到一個 O(n) 算法果然不容易。

3.11 Give an efficient algorithm to determine whether a polygon P with n vertices is monotone with respect to some line, not necessarily a horizontal or vertical one.

到底有沒有可能用單調性質測試單調呢？ O(n log n) 就是極限？讓我們來挑戰挑戰。

Problem

假想一個二維平面，x 軸左右兩側將會射入雷射，現在要將一個簡單多邊形由上往下放入，雷射將會打在第一個碰觸的點上，請問有沒有一種放置方式，使得每一個邊都被雷射覆蓋到。

山形

如上圖，假使這樣放置，位置 (0, 0), (2, 0) 將無法被雷射覆蓋，如果將此圖旋轉 90 度放入，就能覆蓋到所有邊了！因此，決定是否有一個角度放入，能覆蓋到所有邊。

Input

有多組測資，每一組測資第一行將會有一個整數 N，

接下來會有 N 行，每一行上會有一個座標 (x, y)，採用順時針或者逆時針順序。

Output

對於每組測資輸出一行，每一行輸出 yes/no。

Sample Input

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

Sample Output

1
2
yes
no

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
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 <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <string.h>
#include <assert.h>
#include <map>
using namespace std;
#define eps 1e-10
#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 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);
}
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;
}
Pt getIntersect(Pt l1, Pt p1, Pt l2, Pt p2) {
    double a1, b1, c1, a2, b2, c2;
    double dx, dy, d;
    a1 = l1.y, b1 = -l1.x;
    c1 = a1 * p1.x + b1 * p1.y;
    a2 = l2.y, b2 = -l2.x;
    c2 = a2 * p2.x + b2 * p2.y;
    dx = c1 * b2 - c2 * b1, dy = a1 * c2 - a2 * c1;
    d = a1 * b2 - a2 * b1;
    return Pt(dx/d, dy/d);
}
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;
    }
};
struct CMP2 {
    bool operator()(const double &i, const double &j) const {
        if (fabs(i-j) > eps)
            return i < j;
        return false;
    }
};
Seg segs[MAXN];
Pt D[MAXN];
int testMonotone(int n, Pt D[]) {
    int m = 0, origin_n = n;
    D[n] = D[0], D[n+1] = D[1];
    for (int i = 1; i <= n; i++) {
        Pt v1 = D[i + 1] - D[i];
        Pt v2 = D[i - 1] - D[i];
        segs[m++] = Seg(v1, v2, i);
        segs[m++] = Seg(v1 * -1, v2 * -1, i);
    }
    n = m;
    Pt pos = Pt(0, 0);
    set<int> S;
    map<double, vector< pair<int, int> >, CMP2> angle;
    for (int i = 0; i < n; i++) {
        double v1 = atan2(segs[i].s.y - pos.y, segs[i].s.x - pos.x);
        double v2 = atan2(segs[i].e.y - pos.y, segs[i].e.x - pos.x);
        angle[v1].push_back(make_pair(i, 0));
        angle[v2].push_back(make_pair(i, 1));
    }
    double c;
    pair<int, int> u = angle.begin()->second[0];
    Pt fpt;
    if (u.second == 0)  fpt = segs[u.first].s;
    else                fpt = segs[u.first].e;
    for (int i = 0; i < n; i++) {
        if (cross(pos, fpt, segs[i].s) * cross(pos, fpt, segs[i].e) < 0) {
            Pt q = getIntersect(segs[i].s - segs[i].e, segs[i].s, fpt - pos, pos);
            if (dot(q - pos, fpt - pos) > 0)
                S.insert(segs[i].label);
        } 
    }
    for (map<double, vector< pair<int, int> >, CMP2>::iterator it = angle.begin();
         it != angle.end(); it++) {
        for (int i = 0; i < it->second.size(); i++) {
            pair<int, int> u = it->second[i];
            if (u.second == 0)
                c = cross(pos, segs[u.first].s, segs[u.first].e);
            else
                c = cross(pos, segs[u.first].e, segs[u.first].s);
            if (fabs(c) > eps) {
                if (c > 0)
                    S.insert(segs[u.first].label);
                else
                    S.erase(segs[u.first].label);
            }
        }
        if (S.size() >= origin_n - 2)
            return 1;
    }
    return 0;
}
int main() {
    int n;
    double x, y;
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i < n; i++) {
            scanf("%lf %lf", &x, &y);
            D[i] = Pt(x, y);
        }
        int flag = testMonotone(n, D);
        puts(flag ? "yes" : "no");
    }
    return 0;
}
Read More +
解題區/出題解題

[ACM 題目] 少女與戰車

Problem

蘋果樹和梨樹花朵綻放，茫茫霧靄在河面飄揚。出門走到河岸邊，喀秋莎，到那又高又陡的河岸。

一面走著，一面唱著歌兒。唱道草原上空的蒼鷹，唱道她衷心喜愛的男孩。他的來信封封都珍藏。

啊！歌兒，女孩悠揚的歌聲，請跟隨著光明的太陽，飛翔到遙遠前方的戰士，為喀秋莎來向他致意。

願他還記得純情的女孩，願她的歌聲能被聽聞。願他保衛著祖國的大地，而喀秋莎守護著愛情。

蘋果樹和梨樹花朵綻放，茫茫霧靄在河面飄揚。出門走到河岸邊，喀秋莎，到那又高又陡的河岸。

正當梨花開遍了天涯，河上飄著柔曼的輕紗，喀秋莎站在峻峭的岸上，歌聲好像明媚的春光。

姑娘唱著美妙的歌曲，她在歌唱草原的雄鷹，她在歌唱心愛的人兒，她還藏著愛人的書信。

啊，這歌聲姑娘的歌聲，跟著光明的太陽去飛吧，去向遠方邊疆的戰士，把喀秋莎的問候傳達。

駐守邊疆年輕的戰士，心中懷念遙遠的姑娘，勇敢戰鬥保衛祖國，喀秋莎愛情永遠屬於他。

正當梨花開遍了天涯，河上飄著柔曼的輕紗，喀秋莎站在峻峭的岸上，歌聲好像明媚的春光。

現在有 N 台戰車平行奔馳在雪地上，在時間$t = 0$ 時，分別位於$x_{i}$，並且每戰車都維持等速度$v_{i}$，請問有哪幾台曾經在奔馳的過程中當過領先者。

Input

輸入有多組測資，每組第一行會有一個整數 N (N < 32767)。

接著會有 N 行戰車資訊，每一行上會有兩個實數$(x_{i}, v_{i})$，其中$-100,000\le x_{i} \le 100,000$$-100\le v_{i} \le 100$。

Output

對於每組輸出一行，按照輸入順序輸出是否曾經當過領先者，參閱範例輸出。

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
3
5 -1
1 2
3 -3
6
16 0.125
14 0.2727
18 -0.125
4  0.8333
12 0.3
6  0.5714
3
4 1
4 0.5
0 2.25
4
3 0
5 -1
0 0.75
1 0.5

Sample Output

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

hint

Javascript Animation Click It !

example 1
example 2
example 3
example 4

Solution

1
Read More +
解題區/出題解題

[ACM 題目] 災難再臨

Description

Background

還記得那些年我們已經經歷的災難嗎？PTC201410D！ZJOI 2012 DAY2！如果不記得，接著請聽我捏造個故事。

Problem

危險種這一類的怪物，不斷地在村莊肆虐作亂，並且不斷地靠近帝國首都，艾斯德斯大人受令狩獵帝國周圍的危險種。

根據情報顯示，危險種移動的路徑預估為有向無環圖，牠們的數個巢穴坐落於地圖的末端 (也就是不會在有別的地點抵達這個地方)，而在首都前將有數個要塞，要塞正牠們的目標之地。為了阻止牠們到來，身為艾斯德斯大人的下屬，必須派軍隊前往危險種前往要塞的必經之地，即使抵達的位置無法阻止所有巢穴的危險種，但能對艾斯德斯大人貢獻一份心力便已足夠。

由於必經之地很多，好不容易在地圖上標記起來，卻又不知道哪個地點比較好 (可以阻止最多巢穴前往要塞)。正在困擾的同時，艾斯德斯大人已經將全部危險種給剷除了 …

「還沒一瞬間就將怪物解決，艾斯德斯大人啊！ <(_ _)>」

不過報告書還是得寫 …

Input

輸入有多組測資。

每組測資第一行會有一個整數 N (N < 32767)。

接下來會有 N 行，第 i 行上會有數個整數 x，直到 0 表示結束，表示有一條邊從 i 到 x。

Output

對於每組測資，輸出可以埋伏地點以及埋伏的最佳收穫情況。

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
5
0
1 0
1 0
2 3 0
2 0
17
10 13 0
9 12 0
9 14 11 0
10 0
12 0
17 0
0
0
13 14 0
11 0
15 0
15 0
16 0
7 0
16 0
17 0
8 0

Sample Output

1
2
1 1
6 4

Solution

1
Read More +
解題區/出題解題

[ACM 題目] 學姊日談

Description

Background

某 M 正與學姊討論蘿莉控追小海女的故事。

某 M 喃喃自語 …
『用了暴力法來完成的話，就能在調整 O(1) - O(E[x]) 完成。』
『如果用一個最常見的樹鏈剖分來完成也不過是 O(log n) - O(log^2 n)』
『在一般情況下，詢問次數肯定比調整次數來得高，想一想常數還得加上去，完全贏不了啊。』

學姊在一旁說到
『那如果是單純的二元樹，有比較好做嗎？說不定有更簡化的算法來完成？』
『說不定那個 … bitvertor 還是 bitset 能完成呢。』
『這個想法難不成是找到 lowbit 嗎？我沒有暫時想法。』某 M 這麼回答道。
『也許吧 … 我也不確定』學姊簇著眉。

某 M 發了瘋似的想了一個算法
『如果我們將其轉換成 k-ary search tree，也就是說需要將節點編號重新編成有大小關係，然後維護一個 BST 來查找 lower_bound 的結果，這麼一來就是 O(k log n) - O(log n) 了！』
『啊啊啊，這個方法不可行，』
學姊將鄙視般的眼神投向某 M。看來這場病還要持續很久。

『將題目弄成找樹前綴和好了，既然暴力法有期望值的剪枝，讓它剪不了不就好了！』
『你覺得不會被其他解法坑殺嗎 …』學姊如此擔憂地表示到。
『沒關係，吾等 M 可不是說假的』

Problem

給定一棵樹，樹根 root 編號 0，每個點一開始的權重為 0。

操作 x k: 將節點 x 的權重增加 k，請輸出從 x 到 root 的權重和。

Input

輸入有多組測資，每組測資第一行會有一個整數 N (N < 32767)，表示這棵樹有多少個節點。

接下來會有 N - 1 行，每一行上會有兩個整數 u, v (0 <= u, v < N) 表示 u, v 之間有一條邊。

接下來會有一行上有一個整數 Q (Q < 32767)，表示接下來有 M 組詢問。

Output

對於每個詢問結果輸出一行，請參照範例輸出的說明。

每組測資後空一行。

Sample Input

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

Sample Output

1
2
3
4
5
1
3
1
4
12

More

名為 “學姊”。

Solution

1
Read More +
解題區/出題解題

[ACM 題目] 計畫巧遇

Description

Background

正陷入暗戀的蘿莉控，對象正是那小海女 “能年犬”，為了與其相遇，做了一個情報偵測器，但總不能刻意繞道去相遇，這顯然會相當接近跟蹤狂。根據情報網顯示，地圖將會長得跟樹狀圖一樣，接著會有一連串的消息顯示小海女疑似出現的地方，同時也會被驗證是假消息。

能年犬

蘿莉控只想知道如果從 x 點回到家的路上，有沒有機會遇到小海女。如果事先知道將會在哪個場所相遇，就能事先準備。接下來就請你協助他了！

Problem

給定一棵樹，樹根編號 0，每個點一開始的權重為 0，操作有以下兩種。

操作 M x : 將節點 x 的權重從 0->1 或者 1->0。
操作 S x : 輸出從 x 到 root 路徑上，第一個權重為 1 的節點編號。

Input

輸入有多組測資，每組測資第一行會有一個整數 N (N < 32767)，表示這棵樹有多少個節點。

接下來會有 N - 1 行，每一行上會有兩個整數 u, v (0 <= u, v < N) 表示 u, v 之間有一條邊。

接下來會有一行上有一個整數 Q (Q < 32767)，表示接下來有 M 組詢問。

Output

對於每個詢問結果輸出一行，請參照範例輸出的說明。

每組測資後空一行。

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
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
10
0 1
0 2
1 3
0 4
3 5
4 6
5 7
5 8
4 9
10
M 1
S 8
S 4
M 0
M 7
M 9
S 5
M 3
M 8
S 5
31
0 1
0 2
0 3
1 4
1 5
2 6 
2 7
3 8
4 9
4 10
4 11
6 12
6 13
12 14
12 15
13 16
13 17
14 18
14 19
14 20
17 21
17 22
20 23
21 24
21 25
22 26
22 27
23 28
24 29
24 30
10
M 6
S 29
S 9
M 0
S 9
S 6
S 2
M 6
S 29
S 6

Sample Output

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

Solution

1
Read More +
解題區/出題解題

[ACM 題目] 人格分裂

Problem

某 M 現在正在平面座標上的原點 (0, 0)，現在四周被擺放了很多很多鏡子，某 M 可以藉由鏡子與他的人格小夥伴對話，請問那些鏡子可以見到小夥伴。

鏡子可以當作一個線段，之間不會交任何一點，只要能見到該鏡子中一小段區域就算可見到。

備註：不考慮反射看到。

Input

輸入有多組測資。

每組測資第一行將會有一個整數 n (n < 32767)，表示總共有多少個鏡子。
接著會有 n 行，每一行上會有 4 個整數 sx, sy, ex, ey，表示鏡子所在的線段。

(-32767 < sx, sy, ex, ey < 32767)

Output

對於每組測資輸出一行，每一行將會有 n 個整數 (0/1)，分別表示輸入中第 i 個鏡子是否可見到。

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

Sample Output

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

More

sample 2

sample 3

Solution

1
Read More +