解題區►解題區 - UVa

UVa 12858 - Even distribution

Problem

帶小孩子出門旅遊，每到一個地方會得到指定個數的糖果，抵達時必須將糖果均分給每一個小孩才行，現在旅遊並沒有規劃路線，在所有的路線情況下，能攜帶的小孩子個數有多少種情況。

也就是在某些情況，例如攜帶質數個小孩出門，有可能怎麼走都沒辦法均分，而導致小孩之間爭奪糖果的情況。在同一種路線下，會盡可能攜帶最大量的小孩出門。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
2 1
1 9
1 2
4 2
1 2 3 4
1 3
1 2
4 3
30 42 105 70
2 4
1 2
2 3

Sample Output

1
2
3
2
4
11

Solution

Even distribution 均勻分布

對於每一個地方紀錄可以攜帶的小孩數量，用一個 set<int> 維護。

接著不斷地更新走到別的地點，路徑之間取 gcd 最大公因數，然後將所有地點的情況聯集起來即可。

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
#include <stdio.h> 
#include <set>
#include <queue> 
#include <vector>
#include <algorithm>
using namespace std;
int C[65536];
vector<int> g[65536];
int search(int n) {
	set<int> S[65536], UNION;
	queue<int> Q, P;
	int u, v, p, gg;
	for (int i = 0; i < n; i++)
		Q.push(i), P.push(C[i]), S[i].insert(C[i]), UNION.insert(C[i]);
	while (!Q.empty()) {
		u = Q.front(), Q.pop();
		p = P.front(), P.pop();
		for (int i = 0; i < g[u].size(); i++) {
			v = g[u][i];
			gg = __gcd(p, C[v]);
			if (S[v].find(gg) == S[v].end()) {
				S[v].insert(gg), UNION.insert(gg);
				Q.push(v), P.push(gg);
			}
		}
	}
	int ret = UNION.size();
	return ret;
}
int main() {
	int n, m, x, y;
	while (scanf("%d %d", &n, &m) == 2) {
		for (int i = 0; i < n; i++) {
			scanf("%d", &C[i]);
			g[i].clear();
		}
		for (int i = 0; i < m; i++) {
			scanf("%d %d", &x, &y);
			x--, y--;
			g[x].push_back(y);
			g[y].push_back(x);
		}
		printf("%d\n", search(n));
	}
	return 0;
}
/*
2 1
1 9
1 2
4 2
1 2 3 4
1 3
1 2
4 3
30 42 105 70
2 4
1 2
2 3
*/
Read More +
解題區►解題區 - UVa

UVa 12860 - Galaxy collision

Problem

給兩個星座，這兩個星座分別由很多個星星構成，並且在同一個星座的星星之間必須間隔至少大於 5 (歐幾里得距離)。

求其中一個星座最少有幾顆星星。保證輸入一定可以構成兩個星座。

Sample Input

1
2
3
4
5
6
7
8
9
10
6
1 3
9 1
11 7
5 7
13 5
4 4
2
10 10
50 30

Sample Output

1
2
2
0

Solution

看到兩個星座，就很像二分圖，把距離小於等於 5 的點之間連起來，接著二分圖黑白染色，對於每一個連通子圖會得到兩個集合。

根據貪心算法，將每一個連通圖的最小集合加總即可。

但是為了要快速建表，猜測輸入不會太集中，這會造成無法構成兩個星座，因此把圖根據 x 座標儲存，這麼一來只要搜索 [x-5, x+5] 之間的點集即可。

生測資也挺痛苦的。

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
#include <stdio.h> 
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
using namespace std;
vector<int> g[65536];
vector< pair<int, int> > X[524288];
void buildGraph(int x) {
	int d;
	for (int i = X[x].size() - 1; i >= 0; i--) {
		int y = X[x][i].first, u = X[x][i].second;
		for (int j = x - 5; j <= x + 5; j++) {
			if (j < 0)	continue;
			int st = (int)(lower_bound(X[j].begin(), X[j].end(), make_pair(y - 5, -1)) - X[j].begin());
			for (int k = st; k < X[j].size(); k++) {
				if (X[j][k].first > y + 5)	break;
				d = (x-j) * (x-j) + (X[j][k].first - y) * (X[j][k].first - y);
//				d = abs(x-j) + abs(X[j][k].first - y);
				if (d <= 25) {
					if (u != X[j][k].second) {
						g[u].push_back(X[j][k].second);
//						printf("%d -> %d\n", u + 1, X[j][k].second + 1);
					}
				}
			}
		}
	}
}
int visited[65536], dist[65536];
int bfs(int st) {
	queue<int> Q;
	int o[2] = {}, u, v;
	Q.push(st), dist[st] = 1, visited[st] = 1;
	while (!Q.empty()) {
		u = Q.front(), Q.pop();
		o[dist[u]&1]++;
		for (int i = 0; i < g[u].size(); i++) {
			v = g[u][i];
			if (visited[v] == 0)  {
				dist[v] = dist[u] + 1;
				visited[v] = 1;
				Q.push(v);
			}
		}
	}
	return min(o[0], o[1]);
}
int main() {
	int n, x, y;
	while (scanf("%d", &n) == 1) {
		set<int> S;
		for (int i = 0; i < n; i++) {
			scanf("%d %d", &x, &y);
			X[x].push_back(make_pair(y, i));
			S.insert(x);
			visited[i] = 0;
			g[i].clear();
		}
		for (set<int>::iterator it = S.begin();
			it != S.end(); it++)
			sort(X[*it].begin(), X[*it].end());
		for (set<int>::iterator it = S.begin();
			it != S.end(); it++)
			buildGraph(*it);
		int ret = 0;
		for (int i = 0; i < n; i++)
			if (visited[i] == 0)
				ret += bfs(i);
		printf("%d\n", ret);
		for (set<int>::iterator it = S.begin();
			it != S.end(); it++) {
			X[*it].clear();
		}
	}
	return 0;
}
/*
3
1 1
2 2
9 9
2
1 1
2 2
6
1 3
9 1
11 7
5 7
13 5
4 4
2
10 10
50 30
*/
Read More +
解題區►解題區 - UVa

UVa 12639 - Hexagonal Puzzle

Problem

每個六角形會有 1 ~ 6 的數字在每一條邊，可以旋轉六角形，但是相鄰的數字要相同。

請問是否可以拼出目標的形狀。

Sample Input

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

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <map>
using namespace std;
struct Hex {
	int v[6], m[7], rotate;
	int read() {
		for (int i = 0; i < 6; i++) {
			if (scanf("%d", &v[i]) == 1);
			else
				return 0;
		}
		return 1;
	}
	void normal() {
		int t[6], mnexp = 0;
		for (int i = 0; i < 6; i++)
			t[i] = v[i];
		for (int i = 1; i < 6; i++)
			if (t[i] == 1)	mnexp = i;
		for (int i = 0; i < 6; i++)
			v[i] = t[(mnexp + i)%6];
		for (int i = 0; i < 6; i++)
			m[v[i]] = i;
	}
	int getPos(int x) {
		return m[x];
	} 
	int next() {
		return v[(rotate+1)%6];
	}
	int prev() {
		return v[(rotate+5)%6];
	}
	void println() {
		for (int i = 0; i < 6; i++)
			printf("%d ", v[(rotate+i)%6]);
		puts("");
	}
};
int used[7], path[7];
Hex h[7];
int dfs(int idx) {
	if (idx == 7)
		return 1;
//	printf("%d\n", idx);
//	for (int i = 0; i < idx; i++) {
//		printf("%d : ", h[path[i]].rotate);
//		h[path[i]].println();
//	}
//	puts("--");
//	getchar();
	if (idx == 0) {
		for (int i = 0; i < 7; i++) {
			if (used[i] == 0) {
				used[i] = 1;
				path[idx] = i, h[i].rotate = 0;
				if (dfs(idx + 1))	return 1;
				used[i] = 0;
			}
		}
	} else {
		if (idx == 1) {
			for (int i = 0; i < 7; i++) {
				if (used[i] == 0) {
					used[i] = 1;
					path[idx] = i, h[i].rotate = h[i].getPos(h[path[0]].v[idx - 1]);
					if (dfs(idx + 1))	return 1;
					used[i] = 0;
				}
			}
		} else if (idx < 6) {
			for (int i = 0; i < 7; i++) {
				if (used[i] == 0) {
					used[i] = 1;
					path[idx] = i, h[i].rotate = h[i].getPos(h[path[0]].v[idx - 1]);
					if (h[path[idx-1]].prev() == h[i].next())
						if (dfs(idx + 1))	return 1;
					used[i] = 0;
				}
			}
		} else {
			for (int i = 0; i < 7; i++) {
				if (used[i] == 0) {
					used[i] = 1;
					path[idx] = i, h[i].rotate = h[i].getPos(h[path[0]].v[idx - 1]);
					if (h[path[idx-1]].prev() == h[i].next() && h[path[1]].next() == h[i].prev())
						if (dfs(idx + 1))	return 1;
					used[i] = 0;
				}
			}
		}
	}
	return 0;
}
int main() {
	while (true) {
		for (int i = 0; i < 7; i++) {
			if (!h[i].read())
				return 0;
			h[i].normal();
		}
		memset(used, 0, sizeof(used));
		int ret = dfs(0);
		puts(ret ? "YES" : "NO");
	}
	return 0;
}
/*
*/
Read More +
解題區►解題區 - UVa

UVa 11104 - Cousins

Problem

first cousin ：如果兩個字串可以藉由移除不多於一半的字符，可以變成相同的字串。

ex. abcdef、axcyd 分別移除 (b, e, f)、(x, y)，就可以變成 acd。

然而如果它們 string (A, B)要稱為 (n+1)th cousin，則存在一個媒介 C，A 和 C 是 first cousin 以及 B 和 C 是 nth cousin。

Sample Input

1
2
3
4
5
6
7
8
a
b
abb
baa
abcdef
axcyd
0
0

Sample Output

1
2
3
2
2
1

Solution

這題看題看得很痛苦，也就是說找兩個字串最短的關係 (請無視長的)。

然而要如何找到最短的，思考一下絕對跟 LCS 有點關係，想了一整個早上仍然沒有結果，後來看了大神代碼回溯想法：

1
2
3
4
5
6
7
8
9
10
11
12
condition of first cousin for string a, b
* LCS(a, b) = maximum length LCS.
=> check if LCS(a, b) * 2 > a.len && LCS(a, b) * 2 > b.len, then output first cousin.
=> if not, we know string a and string xa which length is LCS(a, b) + a.len.
xa : __LCS(a, b)__ + a.str
	^^^^^^^^^^^^^ // any letters., LCS(a, xa) = a.len, LCS(a, b) <= a.len, so xa and a are first cousins.
and so on, make string x2a which length is LCS(a, b) + 3 * a.len
x2a : __LCS(a, b)__ + a.str + a.str + a.str
	^^^^^^^^^^^^^^^^^^^^^ // any letters., LCS(a, xa) = 2 * a.len, so xa and x2a are first cousisn.
above xa, x2a shown by letter consist, not order.
when x?a can become string b first cousin ? => __LCS(a, b)__ + (? * a.str) = half of b.

仔細想想，這解法類似於貪心？而 LCS 存在的關係是起手用。增倍貪心，把不需要的地方直接填跟目標的內容。

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
int main() {
	char a[128], b[128];
	while (scanf("%s %s", a, b) == 2 && a[0] != '0') {
		int dp[128][128] = {};
		int la = strlen(a), lb = strlen(b);
		for (int i = 0; i < la; i++)
			for (int j = 0; j < lb; j++)
				if (a[i] == b[j])
					dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1);
				else
					dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]);
		int lcs = dp[la][lb];
		int ret = 1, len = lcs;
		if (la > lb)	swap(la, lb);
		while (len + len < lb) {
			len += la, la <<= 1;
			ret++;
		}
		printf("%d\n", ret);
	}
	return 0;
}
/*
condition of first cousin for string a, b
* LCS(a, b) = maximum length LCS.
=> check if LCS(a, b) * 2 > a.len && LCS(a, b) * 2 > b.len, then output first cousin.
=> if not, we know string a and string xa which length is LCS(a, b) + a.len.
xa : __LCS(a, b)__ + a.str
	 ^^^^^^^^^^^^^ // any letters., LCS(a, xa) = a.len, LCS(a, b) <= a.len, so xa and a are first cousins.
and so on, make string x2a which length is LCS(a, b) + 3 * a.len
x2a : __LCS(a, b)__ + a.str + a.str + a.str
	  ^^^^^^^^^^^^^^^^^^^^^ // any letters., LCS(a, xa) = 2 * a.len, so xa and x2a are first cousisn.
above xa, x2a shown by letter consist, not order.
when x?a can become string b first cousin ? => __LCS(a, b)__ + (? * a.str) = half of b.
*/
Read More +
解題區►解題區 - UVa

UVa 10961 - Chasing After Don Giovanni

Problem

A 要追 B，結果 B 偽裝成 C，B 告訴 A，B 將會怎麼走並且沿路指導 A 該怎麼走，然而真正的 C 也會在地圖中某一個地方開始移動。

如果 A、C 相遇，則會發現 B 是偽裝的，給予兩個人的路線，請問 B 是否能安全抵達目的地，如果再目的地被抓到也相當於安全抵達，因為他已經抵達目的地。

假設 A、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
2
2 3
5 2
3
5 4
3 4
3 6
4
4 3
4 5
5 5
5 6
2 2
4 2
3
6 2
6 3
3 3
3
2 4
5 4
5 6

Sample Output

1
2
3
No
Yes

Solution

這一題與 11796 - Dog Distance 很類似。找兩個路線的最接近距離。

  • 题目大意：
    两条狗匀速分别沿着折线跑，已知同时出发，同时到达，问你求相差最大的距离 与相差的最小的距离之间的差值。
  • 解题思路：
    如果两只狗都走1条线段的话，根据相对运动的理论，可以把其中一只狗看成静止不动，另一只狗相对运动，且线路为线段，那么立刻转化为点到线段的距离的问题。
http://blog.csdn.net/a1061747415/article/details/38682243

而這一題檢查最近距離是否為 0 即可。特別 case 終點碰到的情況，此外測資中兩個路線的距離長貌似相同，因為討論區的有幾組不同長的測資，雖然以下代碼沒有通過，但是還是 AC。

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
#include <stdio.h> 
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;
// similar 11796 - Dog Distance
#define eps 1e-8
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;
    }
    bool operator==(const Pt &a) const {
        return fabs(x-a.x) < eps && fabs(y-a.y) < eps;
    }
    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 val) const {
        return Pt(x / val, y / val);
    }
    Pt operator*(const double val) const {
        return Pt(x * val, y * val);
    }
};
typedef Pt Vector;
double dist(Pt a, Pt b) {
	return hypot(a.x - b.x, a.y - b.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);
}
int between(Pt a, Pt b, Pt c) {
	return dot(c - a, b - a) >= 0 && dot(c - b, a - b) >= 0;
}
int onSeg(Pt a, Pt b, Pt c) {
	return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
double distProjection(Pt as, Pt at, Pt s) {
	double a, b, c;
	a = at.y - as.y;
	b = as.x - at.x;
	c = - (a * as.x + b * as.y);
	return fabs(a * s.x + b * s.y + c) / hypot(a, b);
}
double distToSeg(Pt sa, Pt sb, Pt a) {
	if(!(sa == sb) && between(sa, sb, a))
		return distProjection(sa, sb, a);
	return min(dist(sa, a), dist(sb, a));
}
int main() {
	int testcase, cases = 0, A, B;
	Pt DA[105], DB[105];
	scanf("%d", &testcase);
	while(testcase--) {
		scanf("%lf %lf", &DB[0].x, &DB[0].y);
		scanf("%lf %lf", &DA[0].x, &DA[0].y);
		scanf("%d", &A);
		for(int i = 1; i <= A; i++)
			scanf("%lf %lf", &DA[i].x, &DA[i].y);
		scanf("%d", &B);
		for(int i = 1; i <= B; i++)
			scanf("%lf %lf", &DB[i].x, &DB[i].y);
		A++, B++;
		double speed_a = 1, speed_b = 1;
		
		int aIdx, bIdx;
		double sa, sb, run;
		Vector va, vb;
		Pt apos = DA[0], bpos = DB[0];
		aIdx = bIdx = 0;
		
		double mxDist = 0, mnDist = 1e+30;
		while(aIdx < A - 1 && bIdx < B - 1) {
			sa = dist(DA[aIdx+1], apos);
			sb = dist(DB[bIdx+1], bpos);
			run = min(sa/speed_a, sb/speed_b); // run time
			va = (DA[aIdx+1] - apos)/sa * run * speed_a;
			vb = (DB[bIdx+1] - bpos)/sb * run * speed_b;
			if (bpos + vb == DB[B - 1] && apos + va == DA[A - 1]) { // a route is safe even if the villagers meet Leporello at the destination.
				mnDist = min(mnDist, dist(bpos, apos));
				if (!(bpos == bpos+vb-va) && between(bpos, bpos+vb-va, apos) && !(apos == bpos+vb-va))
					mnDist = min(mnDist, distProjection(bpos, bpos+vb-va, apos));
			} else
				mnDist = min(mnDist, distToSeg(bpos, bpos+vb-va, apos));
//			mxDist = max(mxDist, dist(apos, bpos));
//			mxDist = max(mxDist, dist(apos, bpos+vb-va));
			apos = apos + va;
			bpos = bpos + vb;
			if(apos == DA[aIdx+1])
				aIdx++;
			if(bpos == DB[bIdx+1])
				bIdx++;
		}
		if (cases++)	puts("");
		if (fabs(mnDist) < eps)
			puts("No");
		else
			puts("Yes");
	} 
	return 0;
}
/*
*/
Read More +
解題區►解題區 - UVa

UVa 10867 - Cutting a Polygon

Problem

給一個簡單多邊形，接著詢問許多通過兩點的直線，與多邊形的交集長度為何？

Sample Input

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

Sample Output

1
2
3
4
5
2.798
6.000
3.000
2.954
2.000

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
161
#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 {
    	return fabs(x - a.x) < eps && fabs(y - a.y) < eps;
	}
    bool operator<(const Pt &a) const {
		if (fabs(x - a.x) > eps)
			return x < a.x;
		if (fabs(y - a.y) > eps)
			return y < a.y;
		return false;
	}
	double length() {
		return hypot(x, y);
	}
};
double dist(Pt a, Pt b) {
	return (a-b).length();
}
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;
}
int intersection(Pt as, Pt at, Pt bs, Pt bt) {
	if (cross(as, at, bs) * cross(as, at, bt) < -eps &&
		cross(at, as, bs) * cross(at, as, bt) < -eps &&
		cross(bs, bt, as) * cross(bs, bt, at) < -eps &&
		cross(bt, bs, as) * cross(bt, bs, at) < -eps)
		return 1;
	return 0;
}
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;
}
int inPolygon(Pt p[], int n, Pt q) {
    int i, j, cnt = 0;
    for(i = 0, j = n-1; i < n; j = i++) {
        if(onSeg(p[i], p[j], q))
            return 1;
        if(p[i].y > q.y != p[j].y > q.y &&
           q.x < (p[j].x-p[i].x)*(q.y-p[i].y)/(p[j].y-p[i].y) + p[i].x)
           cnt++;
    }
    return cnt&1;
}
double solve(Pt D[], int n, Pt s, Pt e) {
	vector<Pt> p;
	for (int i = 0, j = n - 1; i < n; j = i++) {
		if (cross(s, e, D[i]) * cross(s, e, D[j]) < -eps) {
			Pt t = getIntersect(Seg(D[i], D[j]), Seg(s, e));
			p.push_back(t);
		} else if (onSeg(s, e, D[i]) || fabs(cross(s, e, D[i])) < eps)
			p.push_back(D[i]);
	}
	p.push_back(s);
	p.push_back(e);
	sort(p.begin(), p.end());
	double ret = 0;
	for (int i = 0; i + 1 < p.size(); i++) {
		Pt mid = (p[i] + p[i+1]) * 0.5;
		if (inPolygon(D, n, mid))
			ret += dist(p[i], p[i+1]);
//		printf("%lf %lf ++++\n", p[i].x, p[i].y);
	}
	return ret;
}
int main() {
	int n, m;
	while (scanf("%d %d", &n, &m) == 2 && n) {
		Pt D[2048];
		for (int i = 0; i < n; i++)
			scanf("%lf %lf", &D[i].x, &D[i].y);
		Pt s, e;
		for (int i = 0; i < m; i++) {
			scanf("%lf %lf", &s.x, &s.y);
			scanf("%lf %lf", &e.x, &e.y);
			double ret = solve(D, n, s, e);
			printf("%.3f\n", ret);
		}
	}
	return 0;
}
/*
9 5
0 0
0 2
1 1
2 2
3 1
4 2
5 1
6 2
6 0
-1 2 7.5 1
0 1 6 1
0 1.5 6 1.5
0 2 6 1
0 0 0 2
4 9
0 0 
0 1
1 1
1 0
0 0 1 1
1 1 0 0
0 0 1 0
0 0 0.5 0
0 0.5 1 0.5
0 1 1 1
1 1 1 0
0.75 0.75 0.75 0.25
0 0.25 1 0.75
*/
Read More +
解題區►解題區 - 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 +