解題區/解題區 - UVa

UVa 11184 - Joyful Ride

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;
}
Read More +
解題區/解題區 - UVa

UVa 11106 - Rectilinear Polygon

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
*/
Read More +
解題區/解題區 - UVa

UVa 10877 - Diceoids

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;
}
Read More +
解題區/解題區 - UVa

UVa 10769 - Pillars

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;
}
Read More +
解題區/解題區 - UVa

UVa 10744 - The Optimal Super-Highway

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;
}
Read More +
解題區/解題區 - UVa

UVa 10732 - The Strange Research

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
*/
Read More +
解題區/解題區 - UVa

UVa 10713 - Map

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
*/
Read More +
解題區/解題區 - UVa

UVa 149 - Forests

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
*/
Read More +
解題區/解題區 - UVa

UVa 12240 - Cocircular Points

Problem

You probably know what a set of collinear points is: a set of points such that there exists a straight line that passes through all of them. A set of cocircular points is defined in the same fashion, but instead of a straight line, we ask that there is a circle such that every point of the set lies over its perimeter.

The International Collinear Points Centre (ICPC) has assigned you the following task: given a set of points, calculate the size of the larger subset of cocircular points.

Input

Each test case is given using several lines. The first line contains an integer N representing the number of points in the set (1$\le$N$\le$100). Each of the next N lines contains two integers X and Y representing the coordinates of a point of the set (- 104$\le$X, Y$\le$104). Within each test case, no two points have the same location.

The last test case is followed by a line containing one zero.

Output

For each test case output a single line with a single integer representing the number of points in one of the largest subsets of the input that are cocircular.

Sample Input

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

Sample Output

1
2
3
5 
3 
2

Solution

題目描述：

給平面上 n 個點，最多有多少個點共圓？

題目解法：

窮舉三點拉外心，隨後找共圓的點，最慘會到 O(n^4)。

完全沒有剪枝，也就是說可以刻意將點保留標記，防止窮舉到相同組合，又或者是先按照 x 軸排序，直接在區間內搜索可能的共圓點之類的。

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
#include <stdio.h> 
#include <stdio.h> 
#include <math.h>
#include <string.h>
#include <algorithm>
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 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);
}
Pt circle(Pt a, Pt b, Pt c) {
    Pt mab = (a + b)/2;
    Pt mbc = (b + c)/2;
    Pt lab = b - a, lbc = c - b;
    swap(lab.x, lab.y);
    swap(lbc.x, lbc.y);
    lab.x = -lab.x;
    lbc.x = -lbc.x;
    return getIntersection(mab, lab, mbc, lbc);
}
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);
        }
        int ret = min(2, n);
        for(int i = 0; i < n; i++) {
            for(int j = i + 1; j < n; j++) {
                for(int k = j + 1; k < n; k++) {
                    if(fabs(cross(D[i], D[j], D[k])) < eps)
                        continue;
                    Pt o = circle(D[i], D[j], D[k]);
//					printf("%lf %lf %lf %lf %lf %lf\n", D[i].x, D[i].y, D[j].x, D[j].y, D[k].x, D[k].y);
//					printf("circle %lf %lf\n", o.x, o.y);
                    double d = dist2(o, D[i]);
                    int cnt = 0;
                    for(int p = 0; p < n; p++) {
                        if(fabs(d - dist2(D[p], o)) < eps)
                            cnt++;
                    }
                    ret = max(ret, cnt);
                }
            }
        }
        printf("%d\n", ret);
    }
    return 0;
}
Read More +
解題區/解題區 - UVa

UVa 12206 - Stammering Aliens

Problem

Dr. Ellie Arroway has established contact with an extraterrestrial civilization. However, all efforts to decode their messages have failed so far because, as luck would have it, they have stumbled upon a race of stuttering aliens! Her team has found out that, in every long enough message, the most important words appear repeated a certain number of times as a sequence of consecutive characters, even in the middle of other words. Furthermore, sometimes they use contractions in an obscure manner. For example, if they need to say bab twice, they might just send the message babab, which has been abbreviated because the second b of the first word can be reused as the first b of the second one.

Thus, the message contains possibly overlapping repetitions of the same words over and over again. As a result, Ellie turns to you, S.R. Hadden, for help in identifying the gist of the message.

Given an integer m, and a string s, representing the message, your task is to find the longest substring of s that appears at least m times. For example, in the message baaaababababbababbab, the length-5 word babab is contained 3 times, namely at positions 5, 7 and 12 (where indices start at zero). No substring appearing 3 or more times is longer (see the first example from the sample input). On the other hand, no substring appears 11 times or more (see example 2).

In case there are several solutions, the substring with the rightmost occurrence is preferred (see example 3).

Input

The input contains several test cases. Each test case consists of a line with an integer m (m$\ge$1), the minimum number of repetitions, followed by a line containing a string s of length between m and 40 000, inclusive. All characters in s are lowercase characters from a'' toz’’. The last test case is denoted by m = 0 and must not be processed.

Output

Print one line of output for each test case. If there is no solution, output none; otherwise, print two integers in a line, separated by a space. The first integer denotes the maximum length of a substring appearing at least m times; the second integer gives the rightmost possible starting position of such a substring.

Sample Input

1
2
3
4
5
6
7
3
baaaababababbababbab
11
baaaababababbababbab
3
cccccc
0

Sample Output

1
2
3
5 12
none
4 2

Solution

題目描述：

對於一個字串，找到一段最長子字串出現至少 m 次，若存有多個輸出最右邊位置的子字串。

題目解法：

建造後綴數組，得到高度數組後，二分搜索長度，然後掃描高度數組找尋是否有連續大於等於 m 次的區間。

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
struct SuffixArray {
    int sa[40005], h[40005], n;
    int w[40005], ta[40005], tb[40005];
    char str[40005];
    void sort(int *x, int *y, int m) {
        static int i;
        for(i = 0; i < m; i++)
            w[i] = 0;
        for(i = 0; i < n; i++)
            w[x[y[i]]]++;
        for(i = 1; i < m; i++)
            w[i] += w[i-1];
        for(i = n-1; i >= 0; i--)
            sa[--w[x[y[i]]]] = y[i];
    }
    bool cmp(int *r, int a, int b, int l) {
        if(r[a] == r[b]) {
            if(a+l >= n || b+l >= n)
                return false;
            return r[a+l] == r[b+l];
        }
        return false;
    }
    void build_h() {
        int i, j, k;
        for(i = 0; i < n; i++)  ta[sa[i]] = i;
        for(i = 0; i < n; i++) {
            if(ta[i] == 0) {
                h[ta[i]] = 0;
                continue;
            }
            if(i == 0 || h[ta[i-1]] <= 1)
                k = 0;
            else
                k = h[ta[i-1]]-1;
            while(str[sa[ta[i]-1]+k] == str[sa[ta[i]]+k])
                k++;
            h[ta[i]] = k;
        }
    }
    void build() {// x: rank, y: second key
        int i, k, m = 128, p;
        int *x = ta, *y = tb, *z;
        n = strlen(str);
        x[n] = 0;
        for(i = 0; i < n; i++)
            x[i] = str[i], y[i] = i;
        sort(x, y, m);
        for(k = 1, p = 1; p < n; k *= 2, m = p) {
            for(p = 0, i = n-k; i < n; i++)
                y[p++] = i;
            for(i = 0; i < n; i++) {
                if(sa[i] >= k) {
                    y[p++] = sa[i]-k;
                }
            }
            sort(x, y, m);
            z = x, x = y, y = z;
            for(i = 1, p = 1, x[sa[0]] = 0; i < n; i++)
                x[sa[i]] = cmp(y, sa[i-1], sa[i], k) ? p-1 : p++;
        }
    }
};
SuffixArray in;
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
    int m;
    while(scanf("%d", &m) == 1 && m) {
    	scanf("%s", in.str);
        in.build();
        in.build_h();
        if(m == 1) {
        	printf("%d %d\n", in.n, 0);
        	continue;
    	}
//        for(int i = 0; i < in.n; i++)
//        	printf("%s %d\n", in.str + in.sa[i], in.h[i]);
        int l = 1, r = in.n, mid, ret = -1, retpos;
        while(l <= r) {
        	mid = (l + r)/2;
        	int cnt = 1, mxtime = 0, mxpos = 0;
        	for(int i = 0; i <= in.n; i++) {
        		if(i != in.n && in.h[i] >= mid)
        			cnt++;
        		else {
        			if(mxtime < cnt)
        				mxtime = cnt;
        			if(cnt >= m) {
        				int j = i;
        				do {
        					j--;
        					mxpos = max(mxpos, in.sa[j]);
        				} while(in.h[j] >= mid && j >= 0);
        			}
        			cnt = 1;
        		}
        	}
        	if(mxtime >= m)
        		l = mid + 1, ret = mid, retpos = mxpos;
        	else
        		r = mid - 1;
        }
        if(ret == -1)
        	puts("none");
        else
        	printf("%d %d\n", ret, retpos);
    }
    return 0;
}
/*
1
aaaaa
2
ufzyetzjulljnkbaohjsqpiucxjo
*/
Read More +