解題區►出題解題

[ACM 題目] 障礙物轉換

Problem

在計算幾何領域中，機器人規劃路線是一個實用的議題， 由於機器人是一個有體積的物體，要避開其他的障礙物，障礙物碰撞計算會變得相當複雜。由於某 M 沒有學好這一部分，知道一種方法可以將地圖轉換，把機器人轉換成一個點，計算得到新的障礙物，如此一來就不用處理障礙物碰撞。

從上圖中，一個箭頭型機器人要從左下角移動到右上角，假設不考慮物體可以旋轉，請問是否能移動過去。若把機器人當作一點看待，則必須將物體邊緣增加，變成中間那張圖 configuration space，只剩下一個點和數個多邊形障礙物。接著可以轉換成 visibility graph，把剩下的白色空間進行梯形剖分或者三角剖分，將區域表示成一個點，相鄰區域拉一條邊，就成 dual graph，就能套用一般的最短路徑算法，來協助機器人行走。

處理這問題對於某 M 過於困難，於是將問題更簡化些，只需要把中間那一張圖其中一個障礙物變化求出即可。

現在給定一個凸多邊形障礙物以及移動凸多邊形，假設定位點在深黑色點方形部分，藉由貼著障礙物可以構出新的障礙物，請問新的障礙物為何？

Input

第一行會有一個整數 $T$，表示有多少組測資。

每一組測資會包含兩個凸多邊形。第一行有一個整數 $N$ 表示移動凸多邊形的頂點數量，接下來會有 $N$ 行，每一行會有兩個整數 $x, y$ 表示頂點座標。在 $N+1$ 行之後，會有一個整數 $M$ 表示障礙物凸多邊形的頂點數量，接下來會有 $M$ 行，每一行會有兩個整數 $x, y$ 表示頂點座標。

  • $2 < N, M < 512$
  • $-32767 < x, y < 32767$
  • 假設定位點 (深黑色點方形部分) 都設在原點 (0, 0)。
  • 輸入順序會按照順時針或逆時針給定。

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

Sample Output

1
2
Case #1: 89.0
Case #2: 115.5

Hint

Solution

可以用 $O(nm \log nm)$ 來完成此題，方法很簡單，先將機器人的圖形按照原點旋轉 180 度，接著將障礙物每一個頂點座標加上機器人的座標，總共會得到 $nm$ 的頂點，套用凸包算法求一次即可。

這一題應用 Minkowski Sum 來完成，對於兩個凸多邊形的 Minkowski Sum，可以在 $O(n+m)$ 時間內完成，將兩個凸包採用逆時針儲存，挑選最左，等價時抓下方 y 座標的點，可以知道新凸包的頂點一定是由兩個凸包的頂點 $A_i, B_j$ 疊加而成，一開始抓到的左下方頂點疊加可以得到第一個頂點，接著要按照凸包順序求出，則比較 $(A_i, A_{i+1})$ 和 $(B_j, B_{j+1})$ 哪一個偏的角度小，就挑選哪一個往前推動 i = i+1 或者是 j = j+1。最後就能在 $O(n+m)$ 時間內完成。

假設不是凸多邊形，兩個簡單多邊形最慘會到 $O(n^2 m^2)$。

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

[ACM 題目] 優勢商品

Problem

一份產品有很多屬性，把每一個屬性當作一個維度，當成 $D$ 個維度的向量，當維度越多時絕對支配 (各方面都是最好的) 的機率就越低。若把 $D = 2$，就是在二維空間中的支配點 (Zerojudge d555 平面上的極大點)。由於絕對優勢的產品隨著維度增加而變少，定義出一種相對優勢產品，給定一個 $K$，若 $p_i$ 支配 (k-dominate) $p_j$，必須滿足下列三條：

  • $\exists S’ \subseteq S, |S’| = K$
  • $\forall s_r \in S’, p_i.s_r \geq p_j.s_r $
  • $\exists s_t \in S’, p_i.s_t > p_j.s_t$

用中文解釋這幾條數學公式，假設有 6 個維度的產品，目標 $K = 5$，則表示要在 6 的維度中任意挑選 5 個維度比較，若存在一種挑法可以支配，則可以說 $p_i$ k-dominate $p_j$

例如現在有 8 台筆記型電腦，共有 6 種屬性可以比較，數值越大越好。

Notebook CPU RAM HDD HDD S. Q. VRAM
$N_1$ 3 3 5 6 6 8
$N_2$ 9 4 9 7 7 9
$N_3$ 8 4 7 9 2 7
$N_4$ 5 6 8 9 5 9
$N_5$ 9 7 9 6 2 4
$N_6$ 6 6 6 5 3 5
$N_7$ 5 7 3 8 4 6
$N_8$ 4 4 8 6 6 4

若要判斷 $N_2$ 是否支配 $N_3$，從中挑取 (CPU, RAM, HDD, HDD S., Q.) 這 5 個屬性比較，得到 $N_2$ 勝過於 $N_3$。最後可以發現到 $N_2$ 這產品可以支配 $N_1, N_3, N_5, N_6, N_8$。

現在問題來了，要找到不被任何產品支配的產品 (k-dominant skyline)。如上表 8 項產品的情況，只會有 $N_2, N_4$。

Input

第一行會有一個整數 $T$ 表示有多少組測資。

每一組測資第一行會有三個整數 $N, D, K$，分別表示產品數量、產品屬性種類、以及支配比較的屬性種類。接下來會有 $N$ 行數據，每一行上會有 $D$ 個整數 $s_j$ 表示一個產品的屬性，產品按照輸入順序編號。

  • $N < 1024$
  • $0 < D, K < 8$
  • $0 < s_j < 1000$

Output

對於每組測資輸出一行，輸出該組測資所有的 k-dominant skyline 的產品編號，由小到大輸出。若不存在則輸出 NONE。

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

Sample Output

1
2
3
4
Case #1: 1 2
Case #2: NONE
Case #3: 1
Case #4: 2 4

Solution

這是一篇論文題目 k-dominant skyline set，網路上提出不少算法，看起來都是有容錯率。

這一題只是介紹題，沒有強求高效算法計算，直接 $O(N^2)$ 的比較，稍微優化一下就可以。若要快一點，按照總和由大排到小，從概念上總和越大，表示支配別人的機率越高，那麼根據這種貪心思路去篩選，可以減少很多不必要的比較，速度會更快些。

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

[ACM 題目] 竹馬不敵天降

Problem

「話說，剛剛明明說的是合乎聖誕節的商品。這不是 H-GAME 嗎？哪裡有聖誕元素啊！」
「嗯，真虧你發現這點啊，但還是有點可惜，這是全齡版，沒有工口哦！」
「不管怎麼樣，一點也沒合聖誕節啊。」
「雖然你有好好學習許多東西，但對本質上完全沒有理解。」
「最近開始覺得有點明白了 …」
「那麼就來說明下這個作品吧」
「是一年前發售的大人氣美少女遊戲的續篇吧？」
「是的，那為什麼你沒有察覺到－『一年前』這句話所包含的意義」
「對於期盼著的人那就意味著 … 與戀人時隔一年的再會！」

在 GALGAME 故事發展過程中，竹馬幾乎沒勝過天降，走哪一條線進行發展正是玩 GALGAME 的樂趣。

然而有一款極為糟糕的 GALGAME 的初始方式則是在一開始選定座標下，系統會根據座標找到附近最鄰近少女，並且在隨後的故事情節都會圍繞這名少女。

遊戲的地圖設計很簡單，用一個矩形表示，現在已知 N 名少女的所在地 (都在矩形內部)。一開始選定的座標也必須落在矩形內，請問玩哪每個線路機率分布為何？

Input

輸入有多組測資。

每組第一行會有三個整數 N, A, B，表示在 $[0:A] \times [0:B]$ 地圖中有 N 個已知座標。
接下來會有 N 行，每行上會有兩個整數 x, y，表示每名少女所在的座標 $(x, y)$ 保證不會有重疊的情況。

$$(0 < N \le 100, 0 < A, B \le 1000, 0 \le x \le A, 0 \le y \le B)$$

Output

對於每組測資輸出一行，根據輸入順序輸出每一個故事線的機率。

Sample Input

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

Sample Output

1
2
3
Case 1: 0.500 0.500
Case 2: 0.300 0.700
Case 3: 0.292 0.313 0.396

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
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
#define eps 1e-6 
#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);
    }
    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];
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 calc_convexarea(const vector<Pt> &p) {
    double ret = 0;
    int n = p.size();
    for(int i = 0, j = n - 1; i < n; j = i++)
        ret += p[j].x * p[i].y - p[j].y * p[i].x;
    return fabs(ret /2.0);
}
int main() {
	int n, A, B, cases = 0;
	Pt p[128], mid, vij;
	while (scanf("%d %d %d", &n, &A, &B) == 3) {
		for (int i = 0; i < n; i++)
			scanf("%lf %lf", &p[i].x, &p[i].y);
		printf("Case %d:", ++cases);
		for (int i = 0; i < n; i++) {
			int m = 0;
			vector<Seg> segs;
			segs.resize(n - 1 + 4);
			for (int j = 0; j < n; j++) {
				if (i == j)	continue;
				mid.x = (p[i].x + p[j].x) /2.0;
				mid.y = (p[i].y + p[j].y) /2.0;
				vij.x = mid.x - (p[j].y - p[i].y);
				vij.y = mid.y + (p[j].x - p[i].x);
				segs[m] = Seg(mid, vij), m++;
			}
			segs[m++] = Seg(Pt(0, 0), Pt(A, 0));
			segs[m++] = Seg(Pt(A, 0), Pt(A, B));
			segs[m++] = Seg(Pt(A, B), Pt(0, B));
			segs[m++] = Seg(Pt(0, B), Pt(0, 0));
			vector<Pt> convex = halfPlaneIntersect(segs);
//			for (int j = 0; j < convex.size(); j++)
//				printf("%lf %lf\n", convex[j].x, convex[j].y);
//			puts("--");
			printf(" %.3lf", calc_convexarea(convex) / (A * B));
		}
		puts("");
	}
	return 0;
}
/*
2 5 3
1 2
4 2
2 5 3
1 1
2 2
3 5 3
1 1
2 2
4 1
*/
Read More +
解題區►出題解題

[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 +