Problem

Recycling involves processing used materials into new products in order to prevent the waste of potentially useful materials.

Recycling materials include things like glass, paper, plastic, metal and textiles. There are some materials that can’t be recycled such as Aerosol Cans. Aerosol cans that are not empty may leak or explode during the sorting and baling processes of recycling.

You are given a list of materials to be recycled. The materials are initially aligned in a line one after another. For every type of recyclable-material there is a corresponding bin. You are required to place each recyclable-material in its corresponding bin.

Example:

paper – glass – paper – aerosol – paper

In the example above, there are two types of recyclable-materials (paper & glass) and one type of non-recyclable-material. If we were to pick each material one by one and throw them in the bins, we would require 4 moves since there are 4 recyclable-materials. However, if we remove consecutive items in one move, provided they are of the same type, we could achieve the desired task in lesser number of moves.

Let’s see how this can be done: If we remove the glass first then the first two papers appear side by side enabling them to be moved together in the next move. Then we just have one paper remaining at the end and that requires a further move. This accumulates to a figure of 3 moves.

Illustration:

1
2
3
4

# Start  : paper – glass – paper – aerosol – paper  
# Move 1 : paper – paper – aerosol – paper [ after removing glass ]   
# Move 2 : aerosol – paper  [ after removing first 2 papers ]   
# Move 3 : aerosol [ after removing the last paper ]   

Input

The first line of input is an integer T(T<50) that indicates the number of test cases. Each case starts with an integer N(N<100). The next line contains the names of N materials. The name of each material is a string containing only characters from the set [a..z] and [A..Z] and the length of each is at most 20. A recyclable-material is represented by lowercase letters only and that of non-recyclable-material by uppercase letters only.

Output

For each case, output the case number followed by the minimum number of moves required to clean up all the recyclable-materials meeting the constraints mentioned above.

Sample Input

1
2
3
4
5
6
7

3
5
paper glass paper AEROSOL paper
4
icpc icpc icpc icpc
3
NO RECYCLABLE MATERIALS

Output for Sample Input

1
2
3

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

Solution

題目描述：

現在把垃圾放置在一維空間，垃圾分成可回收和不可回收兩種，我們可以一次將連續個回收物拾起清除 (整個區間內的回收種類都要相同。) 並且放置回收桶。

用小寫表示可回收的種類分布，大寫為不可回收。求操作次數最少為何。

題目解法：

這一題比 UVa 10559 - Blocks 還要稍微簡單一點，可以在 O(n^3) 以內完成。UVa 10559 - Blocks 的計分方式多了一次清除的個數平方，最大化分數。

在這裡我們只需要將狀態改為，考慮區間 [l, r] 最左側 A[l] 項目是否要清除，否則將要等待 [l+1, i] 之間的項目清除之後，與 [i+1, ...] 一起清除。

• 直接移除最左側
• 等待中間一段的移除，隨後跟著 [i+1, ...] 最左側的一起清除。

因此轉移方程

記住中間轉移要保證一定取得連續相同且皆可回收，為了方便計算，連續相同的壓縮起來，直接考慮是否可回收即可。

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

// http://mypaper.pchome.com.tw/zerojudge/post/1326837348
#include <stdio.h>
#include <map>
#include <iostream>
#include <algorithm>
#include <ctype.h>
using namespace std;
int A[105], B[105];
int dp[105][105]; //[l][r][___{l, r}]
char used[105][105] = {}, usedcases = 0;
int dfs(int l, int r) {
    if(l > r)    return 0;
    if(used[l][r] == usedcases)
        return dp[l][r];
    int &ret = dp[l][r];
    used[l][r] = usedcases;
    if(A[l] == -1) {
    	ret = dfs(l + 1, r);
    	return ret;
    }
    ret = dfs(l+1, r) + 1;
    for(int i = l+1; i <= r && A[i] != -1; i++) {
        if(A[i] == A[l]) {
            ret = min(ret, dfs(l+1, i-1) + dfs(i, r));
        }
    }
    return ret;
}
int main() {
    int testcase, n, m;
    int cases = 0, i;
    char material[105][32];
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        
        map<string, int> R;
        for(int i = 0; i < n; i++) {
        	scanf("%s", material[i]);
        	if(islower(material[i][0]))
        		R[material[i]] = 0;
        }
        
        int size = 0;
        for(map<string, int>::iterator it = R.begin(); it != R.end(); it++)
        	it->second = size++;
        for(int i = 0; i < n; i++)	 {
        	if(isupper(material[i][0]))
        		A[i] = -1;
        	else
        		A[i] = R[material[i]];
        }
        
        for(i = 1, B[0] = 1, m = 0; i < n; i++) {
            if(A[m] == A[i])
                B[m]++;
            else {
                A[++m] = A[i], B[m] = 1;
            }
        }
        usedcases++;
        printf("Case %d: %d\n", ++cases, dfs(0, m));
    }
    return 0;
}

Problem

Suppose you want to own a roller coaster. Before you start, you might be interested in designing the course. The course is circular when seen from above, with n towers of equal distances on it. The figure below shows a course with n=7 (numbers inside circles are heights of towers).

To make the towers look interesting, their heights should be distinct positive integers not greater than n+1. To let customers enjoy a large variety of excitement, the height differences between neighboring towers should be all different. Since there are n height differences, each integer value between 1 and n must appear exactly once. In the example above, the height differences are: 8-1=7, 8-2=6, 7-2=5, 7-3=4, 5-3=2, 5-4=1, 4-1=3. You can check that every integer between 1 and 7 appears exactly once.

Write a program to design the ride.

Input

The input consists of several test cases. Each case contains a single integer n (2 £ n £ 1000), the number of towers. The last test case is followed by a single zero, which should not be processed.

Output

For each test case, print the case number and n numbers if the design is possible, ‘-1’ otherwise.

Sample Input

1
2
3

7
234
0

Output for Sample Input

1
2

Case 1: 1 4 5 3 7 2 8
Case 2: -1

Solution

題目描述：

找到一個擺放 N + 1 個數字的環狀，數字彼此之間的差值恰好可以湊出所有 1 到 N 之間的整數。

題目解法：

先窮舉前幾項的可能

Input

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

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

Output

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

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

可以發現，對於 mod 4 餘 3、0 會沒有解。
仔細觀察一下規律，起頭 1，並且分別是 +-+-+- 從 -1+2-3+4 … 類推。

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

#include <stdio.h>
int main() {
	int n, cases = 0;
	while(scanf("%d", &n) == 1 && n) {
		printf("Case %d:", ++cases);
		if(n%4 != 3 && n%4 != 0)
			puts(" -1");
		else {
			int d = (n+1)/4*2-1 + (n%4 == 0);
			int sum = 1 + d;
			printf(" 1 %d", sum);
			for(int i = 1, j = 0; i < n; i++) {
				if(i == d)
					continue;
				if(j%2 != d%2)
					sum += i;
				else
					sum -= i;
				printf(" %d", sum);
				j++;
			}
			puts("");
		}
	}
	return 0;
}

Problem

Given is n points with integer coordinates in the plane. Is it is possible to construct a simple, that is non-intersecting, rectilinear polygon with the given points as vertices? In a rectilinear polygon there are at least 4 vertices and every edge is either horizontal or vertical; each vertex is an endpoint of exactly one horizontal edge and one vertical edge. There are no holes in a polygon.

The first line of input is an integer giving the number of cases that follow. The input of each case starts with an integer 4 ≤ n ≤ 100000 giving the number of points for this test case. It is followed by n pairs of integers specifying the x and y coordinates of the points for this case.

The output should contain one line for each case on input. Each line should contain one integer number giving the length of the rectilinear polygon passing throught the given points when it exists; otherwise, it should contain -1.

Sample input

1
2
3
4
5
6
7
8
9
10

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

Output for sample input

1

12

Solution

題目描述：

給 N 個整數點座標，是否能構成一個直角的簡單多邊形，並請每個點都要在直角上。如果可以構成簡單多邊形，則輸出其多邊形周長為何。

題目解法：

由於每個點都必須在直角上，所以先考慮對 x = k 這一條直線上有數個點，則為了要構成簡單多邊形，保證這數個點根據 y 值排序，一定會構成 (y1, y2) (y3, y4) … 的連線，不然弄不出每一個點都在直角上。同理對於 y = k 考慮連線情況。

當我們將所有連線情況都記錄下後，要確保所有線段之間不會相交 (端點不算在相交情況中)，同時經過遍歷走訪後，所有的點都在同一個 component 上。

對於 N 個線段，可以在 O(N log N) 時間內得到是否有相交情況。代碼修改於 DJWS 演算法筆記

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

#include <stdio.h>
#include <stdio.h> 
#include <math.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
#define eps 1e-6
struct Pt {
    int x, y, label;
    Pt(int a = 0, int b = 0, int c = 0):
    	x(a), y(b), label(c) {}
    bool operator<(const Pt &a) const {
        if(x != a.x)	return x < a.x;
        return y < a.y;
    }
	Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
};
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;
}
int intersection(Pt as, Pt at, Pt bs, Pt bt) {
    if(cross(as, at, bs) * cross(as, at, bt) < 0 &&
       cross(at, as, bs) * cross(at, as, bt) < 0 &&
       cross(bs, bt, as) * cross(bs, bt, at) < 0 &&
       cross(bt, bs, as) * cross(bt, bs, at) < 0)
        return 1;
    return 0;
}
int cmpX(Pt a, Pt b) {
	if(a.x != b.x)	return a.x < b.x;
	return a.y < b.y;
}
int cmpY(Pt a, Pt b) {
	if(a.y != b.y)	return a.y < b.y;
	return a.x < b.x;
}
vector<int> g[100005];
int visited[100005], dfsCnt;
void dfs(int u, int p) {
	visited[u] = 1, dfsCnt++;
	for(int i = g[u].size()-1; i >= 0; i--) {
		int v = g[u][i];
		if(v == p || visited[v])	continue;
		dfs(v, u);
	}
}
// http://www.csie.ntnu.edu.tw/~u91029/PointLinePlane2.html
struct seg {
	Pt s, e;
	seg(Pt a, Pt b):s(a), e(b) {}
};
struct Endpoint {
	int x, s, i;
	Endpoint(int a = 0, int b = 0, int c = 0):
		x(a), s(b), i(c) {}
	bool operator<(const Endpoint &a) const {
		return x < a.x || (x == a.x && s > a.s);
	}
};
struct CMP {
	static int x;
	
	double interpolate(const Pt& p1, const Pt& p2, int& x) {
        if (p1.x == p2.x) return p1.y;
        return p1.y + (double)(p2.y - p1.y) / (p2.x - p1.x) * (x - p1.x);
    }
    
	bool operator()(const seg &i, const seg &j) {
		return interpolate(i.s, i.e, x) < interpolate(j.s, j.e, x);
	}
};
int CMP::x = 0;
set<seg, CMP>::iterator prevNode(set<seg, CMP>::iterator it, set<seg, CMP>& S) {
	return it == S.begin() ? it : --it;
}
set<seg, CMP>::iterator nextNode(set<seg, CMP>::iterator it, set<seg, CMP>& S) {
	return it == S.end() ? it : ++it;
}
bool segment_intersect(vector<seg> segs) {
	for(int i = 0; i < segs.size(); i++)
		if(segs[i].e < segs[i].s)
			swap(segs[i].s, segs[i].e);
			
	vector<Endpoint> e;
	set<seg, CMP> S;
	for(int i = 0; i < segs.size(); i++) {
		e.push_back(Endpoint(segs[i].s.x, 1, i));
		e.push_back(Endpoint(segs[i].e.x, -1, i));
	}
	sort(e.begin(), e.end());
	
	for(int i = 0; i < e.size(); i++) {
		CMP::x = e[i].x;
		if(e[i].s == 1) {
			set<seg, CMP>::iterator it, jt;
			it = S.lower_bound(segs[e[i].i]);
			jt = prevNode(it, S);
			if(it != S.end() && intersection(segs[e[i].i].s, segs[e[i].i].e, it->s, it->e))
				return 1;
			if(jt != S.end() && intersection(segs[e[i].i].s, segs[e[i].i].e, jt->s, jt->e))
				return 1;
			S.insert(segs[e[i].i]);
		} else {
			set<seg, CMP>::iterator it, jt, kt;
			it = S.lower_bound(segs[e[i].i]);
			jt = prevNode(it, S);
			kt = nextNode(it, S);
			if(jt != S.end() && kt != S.end() && intersection(kt->s, kt->e, jt->s, jt->e))
				return 1;
			if(it != S.end())
				S.erase(it);
		}
	} 
	return 0;
}
Pt D[100005], P[100005];
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
	
	int testcase, n;
	scanf("%d", &testcase);
	while(testcase--) {
		scanf("%d", &n);
		for(int i = 0; i < n; i++) {
			scanf("%d %d", &P[i].x, &P[i].y);
			D[i] = P[i], D[i].label = i;
		}
		
		int eflag = 0;
		for(int i = 0; i < n; i++)
			g[i].clear(), visited[i] = 0;
		sort(D, D+n, cmpX);		
		for(int i = 0; i < n && !eflag; i += 2) {
			if(i+1 < n && D[i].x == D[i+1].x) {
				g[D[i].label].push_back(D[i+1].label);
				g[D[i+1].label].push_back(D[i].label);
			} else
				eflag = 1;
		}
		sort(D, D+n, cmpY);
		for(int i = 0; i < n && !eflag; i += 2) {
			if(i+1 < n && D[i].y == D[i+1].y) {
				g[D[i].label].push_back(D[i+1].label);
				g[D[i+1].label].push_back(D[i].label);
			} else
				eflag = 1;
		}
		
		if(!eflag) { // only one component
			dfsCnt = 0;
			dfs(0, -1);
			if(dfsCnt != n)
				eflag = 1;
		}
		
		if(!eflag) {
			vector<seg> segs;
			for(int i = 0; i < n; i++) {
				for(int j = g[i].size()-1; j >= 0; j--) {
					segs.push_back(seg(P[i], P[g[i][j]]));
				}
			}
			eflag = segment_intersect(segs);
		}
		
		if(eflag)
			puts("-1");
		else {
			int para = 0;
			for(int i = 0; i < n; i++) {
				for(int j = g[i].size()-1; j >= 0; j--) {
					para += abs(P[i].x - P[g[i][j]].x) + abs(P[i].y - P[g[i][j]].y);
				}
			}
			printf("%d\n", para/2);
		}
	}
	return 0;
}
/*
5
6
68 81
65 33
32 94
52 80
63 44
11 41
*/

Problem

The following picture shows four dice. Or are they all dice?

Artifacts (a) and (b) are dice; (c) and (d) are not dice, but they are the same—you can see that by a suitable rotation of (d). Thus, here we have two classes of dice-like artifacts (diceoids), classified by comparison under suitable rotations.

You are given a bag of diceoids, and your job is to classify them and report how many classes there are. (Your job is not to determine how many are dice.) To facilitate description of diceoids in a text medium, we label the faces of the cube:

then a diceoid is encoded as a sequence of six numbers dA , . . . , dF , meaning that face i bears di dots. Example: 5 3 6 2 1 4 means that face A has 5 dots, face B has 3 dots, face C has 6 dots, etc. It is entirely possible that different faces have the same number of dots, e.g., 2 2 2 3 3 3, but every face has at least 1 dot and at most 6 dots.

Input

The input file contains several test cases. The description of each test case is given below:

Each test case begins with the number of diceoids n (n<=1000), followed by the description of n dicecoids.

Output

For each test case your program should output the number of classes. Follow the format specified in the output for sample input.

Sample Input

1
2
3
4
5
6
7
8
9

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

Output for Sample Input

1

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

#include<stdio.h>
#include<stdlib.h>
typedef struct {
    int dice[6];
}DICE;
void Right_turn(DICE *A) {
    static int t;
    t = A->dice[0], A->dice[0] = A->dice[4];
    A->dice[4] = A->dice[3], A->dice[3] = A->dice[1], A->dice[1] = t;
}
void Up_turn(DICE *A) {
    static int t;
    t = A->dice[0], A->dice[0] = A->dice[5];
    A->dice[5] = A->dice[3], A->dice[3] = A->dice[2], A->dice[2] = t;
}
void clockwise(DICE *A) {
    static int t;
    t = A->dice[2], A->dice[2] = A->dice[4];
    A->dice[4] = A->dice[5], A->dice[5] = A->dice[1], A->dice[1] = t;
}
DICE Data[2048];
int cmp(const void *a, const void *b) {
    static DICE *i, *j;
    static int k;
    i = (DICE *)a, j = (DICE *)b;
    for(k = 0; k < 6; k++)
        if(i->dice[k] != j->dice[k])
            return i->dice[k] - j->dice[k];
    return 0;
}
void Print(DICE A) {
    static int i;
    for(i = 0; i < 6; i++)
        printf("%d ", A.dice[i]);
    puts("");
}
void Spin_dice(DICE A, int store) {
    static int i, j;
    for(i = 0; i < 6; i++)
        Data[store].dice[i] = A.dice[i];
    for(i = 0; i < 4; i++) {
        for(j = 0; j < 4; j++) {
            if(cmp(&Data[store], &A) > 0)
                Data[store] = A;
            clockwise(&A);
        }        
        Right_turn(&A);
    }
    Up_turn(&A);
    for(i = 0; i < 2; i++) {
        for(j = 0; j < 4; j++) {
            if(cmp(&Data[store], &A) > 0)
                Data[store] = A;
            clockwise(&A);
        }        
        Up_turn(&A), Up_turn(&A);
    }
}
main() {
    int n, i, j;
    DICE A;// 前右上後左下
    while(scanf("%d", &n) == 1 && n) {
        for(i = 0; i < n; i++) {
        	scanf("%d %d %d %d %d %d", &A.dice[0], &A.dice[1], &A.dice[2], 
						&A.dice[3], &A.dice[5], &A.dice[4]);
            Spin_dice(A, i);
        }
        int Ans = 1;
        qsort(Data, n, sizeof(DICE), cmp);
        for(i = 1; i < n; i++) {
            if(cmp(&Data[i], &Data[i-1]))
                Ans++;
        }
        printf("%d\n", Ans);
    }
    return 0;
} 

Problem

The world-famous architect Mr. Fruí from Reus plans to build a colossal pillar H units high. Mr. Fruí has n black pieces with heights b1,…, bn and m white pieces with heights w1,…, wm. According to his design the pillar must have four pieces: a black piece on its bottom, a white piece above it, another black piece above, and finally a white piece on the top of the pillar.

Mr. Fruí wishes to know which of the combinations of four pieces with total height H is the most stable. Given two combinations A = [a1, a2, a3, a4] and B = [b1, b2, b3, b4] (where a1 denotes the height of the bottom (black) piece of the pillar A, a2 denotes the height of the second (white) piece of A, and so on), A is more stable than B if a1 > b1, or if a1 = b1 but a2 > b2, etc. (In other words, A is more stable than B if and only if the sequence of heights of the pieces of A is lexicographically larger than the sequence of heights of the pieces of B.)

Write a program such that, given the desired height H of the pillar, the heights of the black pieces and the heights of the white pieces, computes which pillar (if any) of height exactly H would be the most stable.

Input

Input consists of zero ore more test cases. Each test case has on the first line H, an integer between 1 and 4*108. The second and third lines of each test consist respectively of the sequence b1,…, bn and of the sequence w1,…, wm. A blank line separates two consecutive test cases. You can assume 2$ \le$n$ \le$100 and 2$ \le$m$ \le$100, and that no piece has a height larger than 108.

Output

For every test case, print one line with the sequence of heights of the pieces of the most stable pillar. If no solution exists, print “no solution”.

Sample Input

1
2
3
4
5
6
7

100
20 20
30 10 30 50
 
100
20 10 4
50 30 45

Sample Output

1
2

20 50 20 10
no solution

Solution

題目描述：

這位世界著名的建築師，設計一個黑白相間的柱子，而這個柱子高度必須為 H，並且由四塊石塊來完成，分別是黑 (底部)、白、黑、白 (底部)。

每一種顏色的石塊都有自己的高度，請輸出恰好能組成高度 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

#include <stdio.h> 
#include <string.h>
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#include <sstream>
#include <functional>
using namespace std;
vector<int> getLineNumber(char s[]) {
	stringstream sin(s);
	vector<int> ret;
	int x;
	while(sin >> x)
		ret.push_back(x);
	return ret;
}
int main() {
	char s[1024];
	int H;
	while(gets(s)) {
		sscanf(s, "%d", &H);
		vector<int> B, W;
		gets(s), B = getLineNumber(s);
		gets(s), W = getLineNumber(s);
		gets(s);
		sort(B.begin(), B.end(), greater<int>());
		sort(W.begin(), W.end(), greater<int>());
		
		int f = 0;
		for(int i = 0; i < B.size(); i++)
		for(int j = 0; j < W.size(); j++)
		for(int a = i+1; a < B.size(); a++)
		for(int b = j+1; b < W.size(); b++) {
			if(B[i]+W[j]+B[a]+W[b] == H) {
				printf("%d %d %d %d\n", B[i], W[j], B[a], W[b]);
				i = a = B.size();
				j = b = W.size();
				f = 1;
			}
		}
		if(!f)
			puts("no solution");
	}
	return 0;
}

In our real life when we look for help we find that only a few people are willing to help us but when we look for suggestions there are thousands waiting with their bag of suggestions. In the country named Culabura a similar situation is creating a lot of trouble. Culabura is a country containing around 20000 important places and infinite land area. The president of Culabura wants to build a super highway through his country. This super highway can be expressed by a straight line that fulfills the following two properties:
a) It must be parallel to another road that connects the two most important cities (denoted by A and B) of the country.

b) The summation of distances of all-important places from it must be minimum.

The advisers of the king of Culabura are giving random and meaningless suggestions to solve this problem (As always is the case with advisers). Now your job is to find the minimum summation of distance. For example in the above picture you will have to find the minimum possible value of (d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8). In other words you will have to place the superhighway in such a place so that (d1 + d2 + d3 + d4 + d5 + d6 + d7 + d8) is minimum and you will have print this minimum value. In this problem we will call such minimum value sum_d_min. Your solution must be very efficient. /Looking for an O(n) solution /

Input

The input file contains a single set of input. First line of each input set contains two integers N (0<N<20001) and Q(0<Q<101). Here N is the number of important places and Q is the number of queries. Each of the next N lines contains a pair of integer xi and yi (|xi|, |yi|<=100), where (xi, yi) is the coordinate of the i-th (0<=i<=N-1) important place. Each of the next Q lines contains four integers Ax, Ay, Bx, By, where (Ax, Ay) and (Bx, By) are the coordinates of A and B respectively and the optimal super highway must be parallel to street (or line) AB. You must not consider A and B as part of the N important places. Some important places may be present more than in the list to give them extra importance. You don’t need to worry about that and just consider them as two different places. Also remember that place A and B will always be two different places.

Output

For each query produce one line of output. This line contains the serial of output followed by the value of sum_d_min for that particular query. All the output numbers should be rounded to nearest integer. Look at the output for sample input for details.

Sample Input

1
2
3
4
5
6
7
8
9

6 2
1 1
1 10
20 12
2 4
1 1
2 4
10 10 11 11
2 3 3 4

Output for Sample Input

1
2

Case 1: 15
Case 2: 15

Solution

題目描述：

給平面上 N 個點座標，接著詢問平行兩個點的線中，找到一條當作高速公路，使得每一個點到線上最短距離總和最小。

題目解法：

套用點線距公式，可以發現其符合中位數性質，如果不用中位數的方式，也可以藉由排序後採用 DP 的方式找到一個距離最小的線分布 (線一定會經過其中一個點)。

為了加速，捨棄掉 $\frac{|ax + by + c|}{\sqrt{a^{2}+b^{2}}}$ 的分母部分，留到最後再除即可。

如果只求中位數，可以針對 Selection Algorithm，在 O(n) 時間內找到，速度快於排序的 O(n log 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

#include <stdio.h> 
#include <stdio.h> 
#include <math.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
#define eps 1e-6
struct Pt {
    int x, y;
    Pt(int a = 0, int 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 {
		Pt ret;
		ret.x = x - a.x;
		ret.y = y - a.y;
        return ret;
    }
};
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 distProjection(Pt as, Pt at, Pt s, double &div) {
	long long a, b, c;
	a = at.y - as.y;
	b = as.x - at.x;
	c = - (a * as.x + b * as.y);
	div = a * a + b * b;
	return (a * s.x + b * s.y + c) /* / hypot(a, b) */;
}
int main() {
	int cases = 0, n, q;
	Pt D[32767], a, b;
	while(scanf("%d %d", &n, &q) == 2) {
		for(int i = 0; i < n; i++) {
			scanf("%d %d", &D[i].x, &D[i].y);
		}
		for(int i = 0; i < q; i++) {
			scanf("%d %d", &a.x, &a.y);
			scanf("%d %d", &b.x, &b.y);
			
			vector<double> dist;
			double div;
			for(int j = 0; j < n; j++)
				dist.push_back(distProjection(a, b, D[j], div));
			sort(dist.begin(), dist.end());
			
			double sum = 0, ret;
			for(int j = 0; j < n; j++)
				sum += dist[j] - dist[0];
			ret = sum;
			for(int j = 1; j < n; j++) {
				sum = sum - (dist[j] - dist[j-1]) * (n - j) + (dist[j] - dist[j-1]) * j;
				ret = min(ret, sum);
			}
			printf("Case %d: %.0lf\n", ++cases, ret / sqrt(div));
		}
	}
	return 0;
}
 

Professor A. Karim is working on a project of measuring the surface area of an unknown unearthly object. After a lot of calculation he finds that the surface area of that object is (a+b)(1-ab), where a and b are two parameters related to surface area of that object. With the help of some more advanced experiments he finds N floating-point numbers, which can be possible values of a and b. From the N numbers he can select two values for a and b in NC2 ways (Note that the selections a=2, b=3 and a=3, b=2 are considered same because (a+b)(1-ab) is equal to (b+a)(1-ba)). Karim needs to do some more expensive experiments to find out the real value of a and b, but before doing that he wants to keep only the obvious choices: the selections, which cause the surface of the object to be positive (Greater than zero). Your job is to help Prof. Karim to count how many of the NC2 selections (the value of a and b) causes (a+b)(1-ab) to be positive. Please note that your method must be efficient. (An O(N2) solution will not do)

Input

The input fine contains maximum 7 sets of inputs.

First line of each set contains an integer N (0<N<=10000). Each of the next N lines contains one floating-point number F (|F|<30000.0). The meaning of N is given in the problem statement.

The Input can have the same number twice or even more times. In such cases two same numbers should be considered different.

Input is terminated by a case where the value of N is zero. This case should not be processed.

Output

For each set of input produce one line of output. This line contains the serial no of output followed by an integer which indicates how many of the NC2 selections will cause the value of the expression (a+b)(1-ab) to be positive. Look at the output for sample input for details. You can consider any value greater than 10-15 is positive.

Sample Input

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

5
8197.4013
-3622.8175
-1495.5118
-3958.2735
-678.2750
5
-1208.8234
1465.1943
2699.873
-6665.3587
-4344.6286
0

Output for Sample Input

1
2

Case 1: 10
Case 2: 5

Solution

題目描述：

從一堆數字中，任挑兩個實數出來，計算 (a + b) * (1 + a * b) > 1e-15 的對數有多少個。

題目解法：

固定其中一個數字 a 後，可以找到 b 的一元二次方程式，找到區間解的個數即可。
將輸入的數字排序，二分根的位置即可，但是麻煩的地方在於 > 1e-15，因此這部分做了些許的微調。

// 因為沒有考慮 1e-15 吞了不少 WA。

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

#include <stdio.h> 
#include <math.h>
#include <algorithm>
using namespace std;
#define eps 1e-8
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out2.txt", "w+t", stdout); 
	int n, cases = 0;
	double v[32767];
	while(scanf("%d", &n) == 1 && n) {
		for(int i = 0; i < n; i++)
			scanf("%lf", &v[i]);
			
		sort(v, v+n);
		int ret = 0, pos = 0;
		for(int i = 0; i < n; i++)
			if(v[i] > 0)
				pos ++;
		for(int i = 0; i < n; i++) {
			double a = -v[i], b = (1 - v[i]*v[i]), c = v[i];
			double r1, r2;
			if(b*b - 4*a*c < 0)	continue;
			if(fabs(a) < eps) {
				ret += pos;
				continue;
			}
			r1 = (-b - sqrt(b*b - 4*a*c))/2/a;
			r2 = (-b + sqrt(b*b - 4*a*c))/2/a;
			if(r1 > r2)	swap(r1, r2);
			
			int l = lower_bound(v, v + n, r1) - v;
			int r = upper_bound(v, v + n, r2) - v;
			int cnt = 0;
//			printf("%lf %lf %d %d\n", r1, r2, l, r);
			if(v[i] > 0) { // [l, r)
				while(l >= 0 && (v[l] + v[i])*(1 - v[l]*v[i]) > 1e-15)
					l--;
				l++;
				while(l < n && (v[l] + v[i])*(1 - v[l]*v[i]) <= 1e-15)
					l++;
				while(r < n && (v[r] + v[i])*(1 - v[r]*v[i]) > 1e-15)
					r++;
				if(l <= i && i < r)
					cnt--;
				cnt += r - l;
//				for(int j = 0; j < n; j++) {
//					if(j == i)	continue;
//					if(v[j] > r1 && v[j] < r2)
//						ret++;
//				}
			} else {
				while(l >= 0 && (v[l] + v[i])*(1 - v[l]*v[i]) <= 1e-15)
					l--;
				l++;
				while(l < n && (v[l] + v[i])*(1 - v[l]*v[i]) > 1e-15)
					l++;
				while(r < n && (v[r] + v[i])*(1 - v[r]*v[i]) <= 1e-15)
					r++;
				if(i < l || i >= r)
					cnt--;
				cnt += l + (n - r);
//				for(int j = 0; j < n; j++) {
//					if(j == i) 	continue;
//					if(v[j] < r1 || v[j] > r2)
//						ret++;
//				}
			}
//			int cnt2 = 0;
//			for(int j = 0; j < n; j++) {
//				if(i == j)	continue;
//				cnt2 += (v[i] + v[j]) * (1 - v[i]*v[j]) > 1e-15;
//			}
//			if(cnt != cnt2) {
//				printf("%lf %d %d %lf %lf, %lf %lf\n", v[i], cnt, cnt2, r1, r2, v[l], v[r-1]);
//				return 0;
//			}
			ret += cnt;
		}
		printf("Case %d: %d\n", ++cases, ret/2);
	}
	return 0;
}
/*
2
0
0
*/

Problem

A pirate’s treasure map typically contains a series of instructions which, if followed, lead you from the landing place on a desert isle to the spot marked X where the treasure is buried. You are to construct such a series of instructions for a particular desert isle.

The island is a circle with radius r paces whose centre is at (0,0). Relative to the centre, the point (0,1) is north, (0,-1) is south, (1,0) is east, and (-1,0) is west. Also, (1,1) is northeast, (1,-1) is southeast, (-1,1) is northwest, and (-1,-1) is southwest.

The landing place, on the circumference, is specified by its coordinates. The spot marked X, on the surface of the island is also specified by its coordinates.

Each instruction in the sequence should have the form

direction distance

where direction is one of { north, south, east, west, northeast, northwest, southeast, southwest } and distance is a non-negative real number indicating the number of paces to be travelled in the given direction. When executed as a sequence the instructions should lead from the landing place to the spot marked X without leaving the island. The total distance (that is, the sum of the distances in your sequence) should be minimized. From the possible sequences that minimize total distance, choose one with the minimum number of instructions.

Input will consist of a number of test cases, followed by a line containing -1. Each test case consists of a single line containing five real numbers: r, x, y, X, Y. r is the radius of the island; x,y are the coordinates of the landing place; X,Y are the coordinates of the spot marked X. The landing place and the spot marked X are distinct.

For each test case, output the sequence, one instruction per line. Distances should be accurate to ten places after the decimal, as shown. Output an empty line between test cases.

Sample Input

1
2

100.0 0.0 100.0 25.0 50.0
-1

Possible Output for Sample Input

1
2

south 25.0000000000
southeast 35.3553390593

Solution

題目描述：

在一個圓心島嶼上，給定登陸的座標以及寶藏的位置，只能由 8 個方向的指令，在不跑出陸地的情況下，用最少指令抵達目的地。

題目解法：

很明顯地，保證不超過兩步，但是問題在於要如何不跑出陸地上。

首先，畫一個三角形，保證能用 45 度 + 90 度的情況走到另外一個角，但是對於圓上兩點拉出來平行兩軸的矩形中，能拆分成兩個三角形，對於其中一個做就可以了。

考慮先走 45 度和 90 度其中一個，只會有兩種情況，模擬先走 45 度的情況，查閱是否超出邊界，否則倒序輸出步驟。

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

#include <stdio.h>
#include <math.h> 
#define eps 1e-8 
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
	double r, x1, x2, y1, y2;
	const double sq2 = sqrt(2);
	int cases = 0;
	while(scanf("%lf %lf %lf %lf %lf", &r, &x1, &y1, &x2, &y2) == 5) {
		if(cases++)	puts("");
		double dx = x2 - x1, dy = y2 - y1;
		if(fabs(dx) < fabs(dy)) {
			double diff = fabs(dy) - fabs(dx);
			if(dy < 0) {
				double x = x1 + dx, y = y1 - fabs(dx);
//				printf("%lf %lf\n", x, y);
				if(x*x + y*y > r*r) {
					if(fabs(diff) > eps)
						printf("south %.10lf\n", diff);
					if(dx > 0)
						printf("southeast %.10lf\n", fabs(dx) * sq2);
					if(dx < 0)
						printf("southwest %.10lf\n", fabs(dx) * sq2);
				} else {
					if(dx > 0)
						printf("southeast %.10lf\n", fabs(dx) * sq2);
					if(dx < 0)
						printf("southwest %.10lf\n", fabs(dx) * sq2);
					if(fabs(diff) > eps)
						printf("south %.10lf\n", diff);
				}
			} else {
				double x = x1 + dx, y = y1 + fabs(dx);
				if(x*x + y*y > r*r + eps) {
					if(fabs(diff) > eps)
						printf("north %.10lf\n", diff);
					if(dx > 0)
						printf("northeast %.10lf\n", fabs(dx) * sq2);
					if(dx < 0)
						printf("northwest %.10lf\n", fabs(dx) * sq2);
				} else {
					if(dx > 0)
						printf("northeast %.10lf\n", fabs(dx) * sq2);
					if(dx < 0)
						printf("northwest %.10lf\n", fabs(dx) * sq2);
					if(fabs(diff) > eps)
						printf("north %.10lf\n", diff);
				}
			}
		} else {
			double diff = fabs(dx) - fabs(dy);
			if(dx < 0) {
				double x = x1 - fabs(dy), y = y1 + dy;
				if(x*x + y*y > r*r + eps) {
					if(fabs(diff) > eps)
						printf("west %.10lf\n", diff);
					if(dy > 0)
						printf("northwest %.10lf\n", fabs(dy) * sq2);
					if(dy < 0)
						printf("southwest %.10lf\n", fabs(dy) * sq2);
				} else {
					if(dy > 0)
						printf("northwest %.10lf\n", fabs(dy) * sq2);
					if(dy < 0)
						printf("southwest %.10lf\n", fabs(dy) * sq2);					
					if(fabs(diff) > eps)
						printf("west %.10lf\n", diff);
				}
			} else {
				double x = x1 + fabs(dy), y = y1 + dy;
				if(x*x + y*y > r*r + eps) {
					if(fabs(diff) > eps)
						printf("east %.10lf\n", diff);
					if(dy > 0)
						printf("northeast %.10lf\n", fabs(dy) * sq2);
					if(dy < 0)
						printf("southeast %.10lf\n", fabs(dy) * sq2);
				} else {
					if(dy > 0)
						printf("northeast %.10lf\n", fabs(dy) * sq2);
					if(dy < 0)
						printf("southeast %.10lf\n", fabs(dy) * sq2);					
					if(fabs(diff) > eps)
						printf("east %.10lf\n", diff);
				}
			}
		}
	}
	return 0;
}
/*
    74.584 49.541 55.754 -43.557 -37.453
    74.584 49.541 55.754 23.560 -69.849
    74.584 -40.498 -62.632 0.540 6.183
    74.584 -40.498 -62.632 -14.154 0.389
*/

Problem

The saying You can't see the wood for the trees is not only a cliche, but is also incorrect. The real problem is that you can’t see the trees for the wood. If you stand in the middle of a wood (in NZ terms, a patch of bush), the trees tend to obscure each other and the number of distinct trees you can actually see is quite small. This is especially true if the trees are planted in rows and columns (as in a pine plantation), because they tend to line up. The purpose of this problem is to find how many distinct trees you can see from an arbitrary point in a pine plantation (assumed to stretch for ever).

picture23

You can only see a distinct tree if no part of its trunk is obscured by a nearer tree—that is if both sides of the trunk can be seen, with a discernible gap between them and the trunks of all trees closer to you. Also, you can’t see a tree if it is apparently too small. For definiteness, not too small and discernible gap will mean that the angle subtended at your eye is greater than 0.01 degrees (you are assumed to use one eye for observing). Thus the two trees marked picture169 obscure at least the trees marked picture175 from the given view point.

Write a program that will determine the number of trees visible under these assumptions, given the diameter of the trees, and the coordinates of a viewing position. Because the grid is infinite, the origin is unimportant, and the coordinates will be numbers between 0 and 1.

Input

Input will consist of a series of lines, each line containing three real numbers of the form 0.nn. The first number will be the trunk diameter—all trees will be assumed to be cylinders of exactly this diameter, with their centres placed exactly on the points of a rectangular grid with a spacing of one unit. The next two numbers will be the x and y coordinates of the observer. To avoid potential problems, say by being too close to a tree, we will guarantee that tex2html_wrap_inline260 . To avoid problems with trees being too small you may assume that tex2html_wrap_inline262 . The file will be terminated by a line consisting of three zeroes.

Output

Output will consist of a series of lines, one for each line of the input. Each line will consist of the number of trees of the given size, visible from the given position.

Sample input

1
2

0.10 0.46 0.38
0 0 0

Sample output

1

128

Solution

題目描述：

所有樹木的圓心都在整數座標上，給定每棵樹的直徑和當前所在位置，問能看見多少棵樹木。

能看見的定義為：看到樹兩側邊緣的張角必須大於 0.01 度，同時要跟之前的前方遮蔽的樹木之間保留 0.01 度之間的間隔。

(也就是說樹不能太細瘦，同時看過去的時候不考慮遠方樹木時，要與前方的樹木之間有小縫隙。)

題目解法：

由於有限制張角在 0.01 以上，因此太遠的樹木不用考慮，因此窮舉一部分的樹木即可。

對於窮舉位置的樹木，由距離當前位置的數字由小排到大，開始考慮前方是否有樹木遮蔽，因此把每個樹木的張角 [l, r] 先算出來，接著對於一個樹木，查找是否有距離更近的樹木遮蔽。

對於計算張角的部分 (圓外一點)，有兩種做法

• 算出兩切線的交點，來得到兩交點的所形成的角度，保證不超過 180 度。
• 從起點拉到圓心，算出角度之後，根據切線所形成的三角形，算出 asin 把角度疊加即可。

後者比較簡單，前者雖為本次的計算方式，略為不滿意。

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

#include <stdio.h> 
#include <stdio.h> 
#include <math.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
#define eps 1e-6
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 dist2(Pt a, Pt b) {
	return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(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 getLineIntersection(double a1, double b1, double c1, double a2, double b2, double c2) {
	// a1 x + b1 y + c1 = 0, a2 x + b2 y + c2 = 0
	c1 = -c1, c2 = -c2;
	double d, dx, dy;
	d = a1 * b2 - a2 * b1;
	dx = c1 * b2 - c2 * b1;
	dy = a1 * c2 - a2 * c1;
	return Pt(dx/d, dy/d);
}
void getTangentIntersection(Pt co, double r, Pt p, Pt &pa, Pt &pb) {
	double a, b, c;
	double m1a, m1b, m1c, m2a, m2b, m2c, m1, m2;
	a = r*r - (co.x - p.x) * (co.x - p.x);
	b = 2 * (co.x - p.x) * (co.y - p.y);
	c = r*r - (co.y - p.y) * (co.y - p.y); // am^2 + bm + c = 0
	if(fabs(a) < eps) {
		m2 = (-c)/b;
		m1a = 1, m1b = 0, m1c = - (m1a * p.x + m1b * p.y);
		m2a = m2, m2b = -1, m2c = - (m2a * p.x + m2b * p.y);
	} else {
		m1 = (-b + sqrt(b*b - 4*a*c))/ (2*a);
		m2 = (-b - sqrt(b*b - 4*a*c))/ (2*a);
		m1a = m1, m1b = -1, m1c = - (m1a * p.x + m1b * p.y);
		m2a = m2, m2b = -1, m2c = - (m2a * p.x + m2b * p.y);
	}
	pa = getLineIntersection(m1a, m1b, m1c, m1b, -m1a, -(m1b * co.x + (-m1a) * co.y));
	pb = getLineIntersection(m2a, m2b, m2c, m2b, -m2a, -(m2b * co.x + (-m2a) * co.y));
}
struct Interval {
	Pt p;
	double dist, l, r;
	Interval(double a = 0, double b = 0, double c = 0, Pt d = Pt()):
		dist(a), l(b), r(c), p(d) {
	}
	bool operator<(const Interval &x) const {
		return dist < x.dist;
	}
};
int main() {
	Pt pa, pb, co(1, 1), p(0, 0);
	const double pi = acos(-1);
	double diameter, radius;
	while(scanf("%lf %lf %lf", &diameter, &p.x, &p.y) == 3) {
		if(fabs(diameter) < eps)
			break;
		vector<Interval> interval;
		radius = diameter/2;
		for(int i = -20; i < 20; i++) {
			for(int j = -20; j < 20; j++) {
				getTangentIntersection(Pt(i, j), radius, p, pa, pb);
				double t1, t2;
				t1 = atan2(pa.y - p.y, pa.x - p.x);
				t2 = atan2(pb.y - p.y, pb.x - p.x);
				if(t1 > t2)	swap(t1, t2);
				if(fabs(t1 - t2)*180/pi < 0.01f)
					continue;
				interval.push_back(Interval(pow(pa.x-p.x, 2)+pow(pb.y-p.y, 2), t1, t2, Pt(i, j)));
			}
		}
		sort(interval.begin(), interval.end());
		int ret = 0;
		for(int i = 0; i < interval.size(); i++) {
			double t1 = interval[i].l, t2 = interval[i].r;
			if(t2 - t1 < pi) {
				int f = 1;
				for(int j = 0; j < i; j++) {
					double l = max(t1, interval[j].l), r = min(t2, interval[j].r);
					if(l <= r + 0.01f * pi/180)
						f = 0, j = i;
				}
				ret += f;
			} else {				
				double t3, t4;
				t3 = t2, t4 = pi;
				t2 = t1, t1 = -pi;
				int f = 1;
				for(int j = 0; j < i; j++) {
					double l = max(t1, interval[j].l), r = min(t2, interval[j].r);
					if(l <= r + 0.01f * pi/180)
						f = 0, j = i;
				}
				if(!f)
					continue;
				t1 = t3, t2 = t4;
				for(int j = 0; j < i; j++) {
					double l = max(t1, interval[j].l), r = min(t2, interval[j].r);
					if(l <= r + 0.01f * pi/180)
						f = 0, j = i;
				}
				if(!f)
					continue;
				ret += f;
			}
		}
		printf("%d\n", ret);
	}
	return 0;
}
/*
0.10 0.46 0.38
*/

前提概要

本課程為暑期開課，產學合作的課程。暑期上課各種虐待，反人類行為。

Day 1 虛擬機技術簡介

虛擬化不外乎就是在同一個硬體執行環境下，同時模擬出多個的執行環境，當然不外乎模擬的行為都是間接對機器硬體執行，因此許多指令需要被轉譯，或者是多好幾個步驟來做轉換，因此效率上一定會慢許多。

虛擬化的好處在於，根據硬體的汰換率在維護的費用，每隔固定一段時間就必須增加硬體來服務新的需求，如此一來必須要有更大的空間和電費來部屬伺服器。而且每一台伺服器的功率沒有一直維持高效佔有 (即使 CPU 使用率不高，用電量也不會下降多少，貌似 10% 不到，可以說是少得可憐)。倒不如來整合硬體，根據需求進行分配，同時可以讓需要的空間縮小、電費下降，做到整合到同一台機器上運行，就需要虛擬化的技術。

虛擬化技術分很多層面，最常見的就是在 Host OS 上開始虛擬化的軟體，如 VMware workstation, xen 之類的，在上面可以掛載很多不同的作業系統 Guest OS 執行。在全虛擬化的情況 (如上述)，與一般使用個人電腦沒有什麼差別，所以非常容易入手。半虛擬化效率上又比全虛擬化來得高，在硬體需求上部分不使透過軟體進行，可以在高效率的情況下接軌。

在虛擬化的另一個最常見的就是 JVM，這是在 Application 面向的虛擬化，Java visual machine，提供跨平台等服務，這麼看起來虛擬化無所不在。

虛擬化有幾個困難之處，從經濟面向來看，一開始的轉移到虛擬階段和虛擬化的授權費用太高，畢竟不是所有虛擬化的技術都是 open source。從技術層面來看，虛擬化必須針對硬體做銜接，因此有時候必須靠有限的資源進行組合，才能完成虛擬化的單一功能，因此在初步階段，還必須看 Intel 等硬體架構，是否有考慮虛擬化的設計。在現今，已經有根據虛擬化進行設計，虛擬化也更為普及。

在周邊設備上，虛擬化的架構設計也相當重要，因此部份廠商也搭配他們的驅動程式 driver 進行修改和開源，來方便虛擬化的製作。

但也不是所有情況都適合虛擬化

• 大量計算程序
• 本身的 CPU 就一直維持滿載
• 大量 I/O 的程序
• 原本的執行環境沒有辦法虛擬化 (虛擬化廠商沒有針對其設備)

虛擬化還必須搭載四個主要的功能：

• 多工
• 狀態儲存
• 狀態復原
• 狀態遷徙 (無延遲服務)

虛擬化技術仍有安全疑慮，如何確保資訊安全和風險保證？

平常 VMware workstation 開啟就佔了相當記憶體資源 Orz

Day 2 軟體測試與 VM 測試

用 code coverage 來決定測試好壞，是否能逆向找到 code coverage 的測試情況。

這一天的內容已經在做專題的時候，由指導教授講了好幾次，概念上差不多能理解一大半。

重點為軟體工程的運行面向

• debug
• test-driven develop
• continuous integration

正常大學不會教這些軟工概念，因此在大學畢業進入職場，挺多公司還是會給一段時間來訓練這些運行模式。來教導開發方式和其價值所在，催促人做事必須先教導其價值。

debug 技術而言，從海森堡 BUG、薛丁格 BUG … 等，都是相當有意思的。《BUG 的類型》，知道 BUG 也不見得能修好，這就是現在的情況，而有些 BUG 只會在高階 (過度) 使用者身上才會見到，軟體公司甚至不會想去修 (看看邪惡的微軟便是如此)。從 printf() 開始抓 BUG 的初學技巧，演化到加入中斷點來程序慢慢清除，用 assert() 來防止不符合規格的輸入，用 #ifdef DEBUG 使用 b2g system program 來查閱狀況，雖然不太善用這些技巧，但是 assert() 和 #ifdef DEBUG 偶爾在無法一次掛載在腦部的時候就會採用。

很慶幸，在大學畢業前還有用過這些技巧來 DEBUG，雖然只是在單純的 ACM 解題上使用。

test-driven develop (測試驅動)，這在敏捷開發這套軟工方法中談到。比起程式代碼，測試資料更令人可貴，這也是為什麼挺多大學的開發團隊會藉由參加大型比賽測試資料，來拿不容易收集到的測試資料，單純只是為了測試資料而參加比賽，當然最後主辦單位最後改階段式比賽來發送資料，以免選手罷賽拿資料。

continuout integration (連續整合)，從一部分一部分的代碼中，階段式完成並且測試，確保每一步都是對的，相關的工具很多，來知道每次整合遇到了什麼問題、現在改善什麼 BUG，歷史情況是如何 … 等。

詳見敏捷開發

Day 3 工業電腦虛擬化技術簡介

這一天內容與 Day 1 類似，不過更詳細說明這門課程如何運行，不過看似就會活不下去， 3 人一組在 2 個星期後期中考、4 個星期後期末考，必須要完成的 Final project。

升大四修碩班課程果然還有點落差，問題在於資源上沒有實驗室的協助，要怎麼將實習課所需要的虛擬機器的伺服器弄出來？助教講得很輕鬆，真正有資源來完成要求的人卻很少呢。

1. Github 使用
2. RedMine 協助

第一點有在用，但是不專精，對我來說目前只當作是垃圾倉庫使用中。還真是慘不忍睹。

Day 4 軟體容錯 與 NCU - FTVM

1. 虛擬容錯的處理器環境要相同，是否是相當嚴苛的條件，而這個容錯只在於軟體掛點的時候，轉移狀態給另外一台虛擬機進行程序接手，在存取空間是共用的，因是為存取空間的備份不容易完成嗎？
2. 由於容錯功能不能與許多功能兼容，是否會造成無法長時間處於容錯狀態？