解題區►解題區 - 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 +
學校課程►通識課程

[通識] 文明的進程 Week 9

心得

請閱讀 梁文道：媚俗，並寫出：你覺得台灣媒體中最常出現哪些情感字眼？反映了怎樣的情感專制呢？（100字）

文章中描述有關 激動 、 動情 兩字的使用，呈現一種媚俗的表現，

媚俗（德語：Kitsch）是一種被視為次等的視覺藝術形式，對現存藝術風格欠缺品味地作複製，又或是對已獲廣泛認同的藝術作毫無價值的模仿。
媚俗這個概念最初所描述的一類藝術作品，是對19世紀在美學上傳達誇張的傷悲和情緒的藝術手法（例如通俗劇）的一種回應，所以，「媚俗藝術」和「傷感藝術」有密切關係。

那篇文章是在 2010 年寫的，至今也有 4 年多的時間，而現今正在選舉當頭，而在經歷食安風暴的那段日子，新聞中最常出現的一詞為 痛批 ，這一詞是由新聞媒體創造出來的，在其他文本中是沒有任何中文字詞解釋。

其實這一詞等同於 回應 ，但是又增添了情感上的強化，呈現一種委屈、於心不忍的回應，有一種 明明對你這麼好，為什麼你居然這麼對我 。儘管當事者並沒有這樣的情感，但仍然是作為為某些族群發聲的言論，亦或是一種包裝罵人的態度。

越來越少見到苛責、辱罵、… 等，一種單方面說明對方不好之處， 痛批 一詞給予發言人背景、地位，讓人覺得他說話必然有其理由、逼不得已說出這樣的話來。

直接地情緒化辱罵的發言，都將用 痛批 來包裝過於單一情緒化不理智的發言，也就是課程講的內容，我們再也無法直視情緒，任何不理智的情緒都必須被美化成另外一種較為平靜的情感。

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 +
解題區►解題區 - UVa

UVa 12551 - Shares

Problem

現在要購買股票，每一個股票都有其花費和預期的在未來的出售價格。

但是股票採用組合包的方式進行販售，但是每一種組合包都只能購買一次，請問在資金只有 C 元的情況下，最多能在未來淨利多少。

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
500
4 6
10 15
8 6
20 15
12 12
3 1 6 2 7 3 8
3 3 8 1 10 2 4
3 4 10 2 5 1 10
2 1 4 2 4
1 3 2
2 4 3 2 1
200000000
5 30
2800 3500
1400 4800
2900 2800
500 3800
3300 4700
2 2 13 4 15
4 4 1 1 22 3 17 5 22
1 3 2
1 3 6
4 1 11 2 5 3 7 5 15
1 5 1
4 2 26 1 21 3 8 5 26
2 3 5 2 26
4 2 30 4 12 3 7 5 14
3 3 8 2 20 5 3
1 5 30
2 1 29 3 3
5 3 3 1 20 5 26 4 9 2 25
3 1 2 2 16 3 5
2 5 5 4 26
5 2 18 5 10 4 18 1 12 3 30
3 2 5 3 27 5 4
4 3 2 4 8 1 20 2 6
3 2 14 1 1 4 22
5 2 23 3 26 1 27 5 3 4 6
1 2 16
4 1 13 4 10 2 23 5 2
1 1 14
1 2 20
1 3 14
2 3 21 1 22
1 2 27
3 5 24 1 26 3 13
5 4 15 3 3 2 21 1 5 5 16
4 2 22 5 1 4 10 1 30

Sample Output

1
2
52
2168800

Solution

每個東西只能購買一次，可見是一個 01 背包問題，但是由於 C 很大，也就是背包容量過大，導致 DP 上的困難。

但是題目並沒有特別說明測資的特殊性，後來才得知可以用 gcd 最大共同因數去降，就是縮小幣值，相當於換外國幣去思考。這麼一來 C 可以降很多，但在一般的背包問題中，gcd 的效應並不高。

把我的純真還回來啊，不想自己 yy 測資特殊性。

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
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
	int C, n, m;
	int x, s, q;
	int cost[512], profit[512];
	int cases = 0;
	while (scanf("%d", &C) == 1) {
		scanf("%d %d", &n, &m);
		for (int i = 1; i <= n; i++)
			scanf("%d %d", &cost[i], &profit[i]), profit[i] -= cost[i];
		vector< pair<int, int> > items;
		for (int i = 0; i < m; i++) {
			scanf("%d", &x);
			int c = 0, p = 0;
			for (int j = 0; j < x; j++) {
				scanf("%d %d", &s, &q);
				c += cost[s] * q;
				p += profit[s] * q;
			}
			if (c <= C && p > 0)
				items.push_back(make_pair(c, p));
		}
		if (cases++)	puts("");
		if (items.size() == 0) {
			puts("0");
			continue;
		}
		if (items.size() == 1) {
			printf("%d\n", items[0].second);
			continue;
		}
		int g = C;
		for (int i = 0; i < items.size(); i++)
			g = __gcd(g, items[i].first);
		C /= g;
		for (int i = 0; i < items.size(); i++)
			items[i].first /= g;
		vector<int> dp(C + 1, 0);
		for (int i = 0; i < items.size(); i++) {
			for (int j = C; j >= items[i].first; j--)
				dp[j] = max(dp[j], dp[j - items[i].first] + items[i].second);
		}
		printf("%d\n", dp[C]);
	}
	return 0;
}
/*
500
4 6
10 15
8 6
20 15
12 12
3 1 6 2 7 3 8
3 3 8 1 10 2 4
3 4 10 2 5 1 10
2 1 4 2 4
1 3 2
2 4 3 2 1
200000000
5 30
2800 3500
1400 4800
2900 2800
500 3800
3300 4700
2 2 13 4 15
4 4 1 1 22 3 17 5 22
1 3 2
1 3 6
4 1 11 2 5 3 7 5 15
1 5 1
4 2 26 1 21 3 8 5 26
2 3 5 2 26
4 2 30 4 12 3 7 5 14
3 3 8 2 20 5 3
1 5 30
2 1 29 3 3
5 3 3 1 20 5 26 4 9 2 25
3 1 2 2 16 3 5
2 5 5 4 26
5 2 18 5 10 4 18 1 12 3 30
3 2 5 3 27 5 4
4 3 2 4 8 1 20 2 6
3 2 14 1 1 4 22
5 2 23 3 26 1 27 5 3 4 6
1 2 16
4 1 13 4 10 2 23 5 2
1 1 14
1 2 20
1 3 14
2 3 21 1 22
1 2 27
3 5 24 1 26 3 13
5 4 15 3 3 2 21 1 5 5 16
4 2 22 5 1 4 10 1 30
*/
Read More +
解題區►解題區 - UVa

UVa 12550 - How do spiders walk on water

Problem

一個可以行走在靜止水面上的蜘蛛，現在要靠近瀑布，瀑布會於鄰近周圍會產生流速。

蜘蛛最多可以在 P 速度的水面上前進，請問最近可以靠近瀑布多少。現在已知從靜止水面靠近瀑布的部分流速，在未知的部分根據觀察是前面單位距離 1 距離 2 的線性關係。($v_{i} = a v_{i-1} + b v_{i-2}$)

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
3 3 0 1 1 1
10 2 0 1 1 2
10 3 0 1 1 2
10 4 0 1 1 2
10 5 0 1 1 2
10 6 0 1 1 2
10 7 0 1 1 2
10 8 0 1 1 2
10 9 0 1 1 2
10 3 1 1 2 2 2 3 3 3 3 4 4
10 5 1 1 2 2 2 3 3 3 3 4 4
10 5 6 6 6 6 8 8 8 11 30 41 42
10 2 0 1 1 1 1 1 1 1 1 1 1
50 200 0 3 6 15 36

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
The spider may fall!
7
6
6
5
5
5
4
4
2
The spider may fall!
The spider is going to fall!
The spider may fall!
45

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
#include <stdio.h> 
#include <algorithm>
#include <sstream> 
#include <iostream>
using namespace std;
char line[1048576];
pair<double, double> solve(double a1, double b1, double c1, double a2, double b2, double c2) {
	// a1 x + b1 y = c1, a2 x + b2 y = c2
	double dx, dy, d;
	d = a1 * b2 - b1 * a2;
	dx = c1 * b2 - b1 * c2;
	dy = a1 * c2 - a2 * c1;
	return make_pair(dx / d, dy / d);
}
int main() {
	int D, P;
	while (gets(line)) {
		stringstream sin(line);
		sin >> D >> P;
		double d[32767];
		int n = 0;
		while (sin >> d[n])	n++;
		int pos = 0;
		if (n < D + 1) {
			pair<double, double> sol = solve(d[n-4], d[n-3], d[n-2], d[n-3], d[n-2], d[n-1]);
//			printf("%lf %lf\n", sol.first, sol.second);
			for (int i = n; i < D + 1; i++, n++) {
				d[i] = sol.first * d[i-2] + sol.second * d[i-1];
				if (P < d[i])	break;
			}
		}		
		for (int i = 0; i < D + 1; i++) {
			if (P < d[i])	break;
			pos++;
		}
		if (pos == D + 1)
			puts("The spider may fall!");
		else if (pos == 0)
			puts("The spider is going to fall!");
		else
			printf("%d\n", D - pos + 1);
	}
	return 0;
}
/*
*/
Read More +
解題區►解題區 - UVa

UVa 12094 - Battle of the Triangle

Problem

平面上有士兵和戰車，分別有 S 個、T 個，接著會有 Q 組詢問，每組詢問有三條線，每組詢問之間的線保證斜率會彼此相同 (只是移動線，這需求非常奇怪。)，請問三條線拉出的 7 個區域中，中間與外側三塊地士兵、戰車個數差異為何？

Sample Input

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

Sample Output

1
2
3
Battle Field 1:
Query 1: 1 -2
Query 2: 1 -1

Solution

先獲得需要劃分的斜率，對三種斜率進行點的排序，因此對得到六個排序結果 (士兵和戰車)。之後就能在排序結果中，二分搜尋該線的左側、右側分別有多少點。

解決這個之後，要來看看噁心的排容原理，這裡還是建議參照 flere 的圖示：

對於拉出的三角形三個交點編號 A, B, C，接著對其做區域編號，

(1) BC 線段的左邊 有區域 1 2 3 6
(2) AC 線段的左邊 有區域 2 6 7
(3) AB 線段的下面 有區域 2 3 4
(1) - (2) - (3) 就可以得到區域 1 - 2 - 7 - 4
就是我們要的答案

flere

在程式邏輯上，挑一點與其一線同側，另兩條線與點異側。

沒有辦法單獨對區域內部搜尋點個數，然後統計完再相減，即使使用 range query，也無法在有效時間內完成任意三角形的範圍搜索 (矩形可以考慮，用等腰直角三角形也好。)。

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
#include <stdio.h> 
#include <stdio.h> 
#include <math.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
#define eps 1e-6
const double pi = acos(-1); 
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}
    bool operator<(const Pt &a) const {
        if(fabs(x-a.x) > eps)
            return x < a.x;
        return y < a.y;
    }
    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);
    }
};
double dist(Pt a, Pt b) {
	return hypot(a.x - b.x, a.y - b.y);
}
double length(Pt a) {
	return hypot(a.x, a.y);
}
double dot(Pt a, Pt b) {
	return a.x * b.x + a.y * b.y;
}
double cross2(Pt a, Pt b) {
	return a.x * b.y - a.y * b.x;
}
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 angle(Pt a, Pt b) {
	return acos(dot(a, b) / length(a) / length(b));
}
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);
}
Pt getIntersection(Pt p, Pt l1, Pt q, Pt l2) {
	double a1, a2, b1, b2, c1, c2;
	double dx, dy, d;
	a1 = l1.y, b1 = -l1.x, c1 = a1 * p.x + b1 * p.y;
	a2 = l2.y, b2 = -l2.x, c2 = a2 * q.x + b2 * q.y;
	d = a1 * b2 - a2 * b1;
	dx = b2 * c1 - b1 * c2;
	dy = a1 * c2 - a2 * c1;
	return Pt(dx / d, dy / d);
}
struct Line {
	int A, B, C;
	bool operator<(const Line &a) const {
		double t1 = atan2(B, A);
		double t2 = atan2(a.B, a.A);
		if (t1 < 0)	t1 += pi;
		if (t2 < 0)	t2 += pi;
		return t1 < t2;
	}
};
Pt getIntersection(Line l1, Line l2) {
	double a1, a2, b1, b2, c1, c2;
	double dx, dy, d;
	a1 = l1.A, b1 = l1.B, c1 = -l1.C;
	a2 = l2.A, b2 = l2.B, c2 = -l2.C;
	d = a1 * b2 - a2 * b1;
	dx = b2 * c1 - b1 * c2;
	dy = a1 * c2 - a2 * c1;
	return Pt(dx / d, dy / d);
}
struct cmp {
	static Line base;
	bool operator() (const Pt &p1, const Pt &p2) const {
		double c1, c2;
		c1 = p1.x * base.A + p1.y * base.B;
		c2 = p2.x * base.A + p2.y * base.B;
		if (fabs(c1 - c2) > eps)
			return c1 < c2;
		return false;
	}
};
Line cmp::base;
int main() {
	int cases = 0;
	int n, m, q;
	double x, y;
	while (scanf("%d %d %d", &n, &m, &q) == 3 && n) {
		vector<Pt> soldiers, tanks;
		vector<Pt> soldier[3], tank[3];
		Line Q[10000][3];
		for (int i = 0; i < n; i++) {
			scanf("%lf %lf", &x, &y);
			soldiers.push_back(Pt(x, y));
		}
		for (int i = 0; i < m; i++) {
			scanf("%lf %lf", &x, &y);
			tanks.push_back(Pt(x, y));
		}
		for (int i = 0; i < q; i++) {
			for (int j = 0; j < 3; j++) {
				scanf("%d %d %d", &Q[i][j].A, &Q[i][j].B, &Q[i][j].C);
				if (Q[i][j].A < 0 || (Q[i][j].A == 0 && Q[i][j].B < 0)) {
					Q[i][j].A = -Q[i][j].A;
					Q[i][j].B = -Q[i][j].B;
					Q[i][j].C = -Q[i][j].C;
				}
			}
			sort(Q[i], Q[i] + 3);
		}
		for (int i = 0; i < 3; i++) {
			soldier[i] = soldiers;
			tank[i] = tanks;
			cmp::base = Q[0][i];
			sort(soldier[i].begin(), soldier[i].end(), cmp());
			sort(tank[i].begin(), tank[i].end(), cmp());
		}
//		for (int i = 0; i < 3; i++) {
//			for (int j = 0; j < soldier[i].size(); j++)
//				printf("%.2lf %.2lf ,", soldier[i][j].x, soldier[i][j].y);
//			puts("\n--++--");
//		}
		printf("Battle Field %d:\n", ++cases);
		for (int i = 0; i < q; i++) {
//			for (int j = 0; j < 3; j++)
//				printf("%d %d %d -\n", Q[i][j].A, Q[i][j].B, Q[i][j].C);
			Pt pabc[3];
			pabc[0] = getIntersection(Q[i][1], Q[i][2]); // bc
			pabc[1] = getIntersection(Q[i][0], Q[i][2]); // ac
			pabc[2] = getIntersection(Q[i][0], Q[i][1]); // ab
			int ret1 = 0, ret2 = 0;
			int tmp[3];
			for (int j = 0; j < 3; j++) {
				cmp::base = Q[i][j];
				tmp[j] = (int)(lower_bound(soldier[j].begin(), soldier[j].end(), 
				pabc[(j+1)%3], cmp()) - soldier[j].begin());
				int v1 = (Q[i][j].A * pabc[j].x + Q[i][j].B * pabc[j].y + Q[i][j].C < 0);
				int v2 = (Q[i][j].A * soldier[j][0].x + Q[i][j].B * soldier[j][0].y + Q[i][j].C < 0);
				int v3 = (Q[i][j].A * soldier[j][soldier[j].size()-1].x + Q[i][j].B * soldier[j][soldier[j].size()-1].y + Q[i][j].C < 0);
					
				if (j == 0)  {
					if (tmp[j]) {
						if (v1 != v2)
							tmp[j] = soldier[j].size() - tmp[j];
					} else {
						if (v1 == v3)
							tmp[j] = soldier[j].size() - tmp[j];
					}
				} else {
					if (tmp[j]) {
						if (v1 == v2)
							tmp[j] = soldier[j].size() - tmp[j];
					} else {
						if (v1 != v3)
							tmp[j] = soldier[j].size() - tmp[j];
					}
				}
//				printf("[%d] soldier %d\n", j, tmp[j]);
			}
			ret1 = tmp[0] - tmp[1] - tmp[2];
			for (int j = 0; j < 3; j++) {
				cmp::base = Q[i][j];
				tmp[j] = (int)(lower_bound(tank[j].begin(), tank[j].end(), 
				pabc[(j+1)%3], cmp()) - tank[j].begin());
				int v1 = (Q[i][j].A * pabc[j].x + Q[i][j].B * pabc[j].y + Q[i][j].C < 0);
				int v2 = (Q[i][j].A * tank[j][0].x + Q[i][j].B * tank[j][0].y + Q[i][j].C < 0);
				int v3 = (Q[i][j].A * tank[j][tank[j].size()-1].x + Q[i][j].B * tank[j][tank[j].size()-1].y + Q[i][j].C < 0);
					
				if (j == 0)  {
					if (tmp[j]) {
						if (v1 != v2)
							tmp[j] = tank[j].size() - tmp[j];
					} else {
						if (v1 == v3)
							tmp[j] = tank[j].size() - tmp[j];
					}
				} else {
					if (tmp[j]) {
						if (v1 == v2)
							tmp[j] = tank[j].size() - tmp[j];
					} else {
						if (v1 != v3)
							tmp[j] = tank[j].size() - tmp[j];
					}
				}
//				printf("[%d] tank %d\n", j, tmp[j]);
			}
			ret2 = tmp[0] - tmp[1] - tmp[2];
			printf("Query %d: %d %d\n", i+1, ret1, ret2);
		}
	}
	return 0;
}
/*
8 5 2
-1 8
-7 3
-2 1
-2 -1
-5 -2
6 -1
2 -4
-4 -5
1 7
1 1
3 4
-6 5
-12 -6
2 -2 10
-2 6 6
-5 -3 1
1 -1 5
1 -3 -3
5 3 -15
0 0 0
*/
Read More +