HOJ 2704 Phone Cell
题目大意：给定圆的半径，以及平面上的一些点的坐标，问用此半径的圆最多可覆盖平面上多少点
我的做法：首先枚举一个圆与其他圆的相交情况，记录两圆相交的弧，也就是记录两个交点对于圆心的极角，并且作上标记，进入的点为+1，退出的点为-1。那么对于每个圆可以得到若干个极角的区间，所以排序之后再扫描一遍，遇到进入的点计数器+1，遇到退出的计数器-1，每次都动态更新最大值就可以了。在其中要注意当两点极角跨越0极角的时候会出现问题，所以可以将所有的极角都扩大到[0, 4π)上，即所有的极角都加2π，然后进行统计即可。
Code：
1
#include <iostream>
2
3#include <cmath>
4
5#define N 8096
6
7#define M 2024
8
9using namespace std;
10
11int n;
12
13double R;
14
15const double pi( acos(-1.0));
16
17struct point
18
19
{
20
21 int x, y;
22
23
}p[M];
24
25struct seg
26
27{
28
29 double apha;
30
31 int flag;
32
33}s[N];
34
35bool cmp(seg a, seg b)
36
37{
38
39 return a.apha < b.apha;
40
41}
42
43int main()
44
45{
46
47 while (scanf("%d %lf", &n, &R) == 2 )
48
49
{
50
51 if(n == 0 && R == 0) break;
52
53 for (int i(0); i < n; i++)
54
55 scanf("%d %d", &p[i].x, &p[i].y);
56
57 R = R + 0.001;
58
59 int cnt = 0;
60
61 int ans = 0, sum = 0;
62
63 point tp;
64
65 double dist, a1, a2;
66
67 for (int i(0); i < n; i++)
68
69 {
70
71 cnt = 0;
72
73 for (int j(0); j < n; j++)
74
75 {
76
77 if (i == j)
78
79 continue;
80
81 tp.x = p[i].x - p[j].x;
82
83 tp.y = p[i].y - p[j].y;
84
85 dist = sqrt(tp.x * tp.x + tp.y * tp.y);
86
87
88
89 if(dist <= 2 * R)
90
91 {
92
93 double ang = atan2(p[j].y - p[i].y, p[j].x - p[i].x);
94
95 if(ang < 0) ang += 2 * pi;
96
97 double tpa = acos(dist / (2 * R));
98
99 a1 = ang + tpa + 2 * pi;
100
101 a2 = ang - tpa + 2 * pi;
102
103 s[cnt].apha = a2, s[cnt].flag = 1;
104
105 cnt++;
106
107 s[cnt].apha = a1, s[cnt].flag = 0;
108
109 cnt++;
110
111
}
112
113 }
114
115 if (ans >= cnt / 2)
116
117 continue;
118
119 sort(s, s + cnt, cmp);
120
121 sum = 0;
122
123 for (int j(0); j < cnt; j++)
124
125 {
126
127 if (s[j].flag) sum ++;
128
129 else sum --;
130
131 if(sum > ans) ans = sum;
132
133 }
134
135 }
136
137 printf("It is possible to cover %d points.\n", ans + 1);
138
139 }
140
141 return 0;
142
143}
144
145
HOJ 1799 Circle and points 做法同上题一样
1#include <iostream>
2
3#include <cmath>
4
5#include <algorithm>
6
7#define N 8096
8
9#define M 2024
10
11using namespace std;
12
13int n;
14
15double R;
16
17const double pi( acos(-1.0));
18
19struct point
20
21{
22
23 double x, y;
24
25}p[M];
26
27struct seg
28
29{
30
31 double apha;
32
33 int flag;
34
35}s[N];
36
37bool cmp(seg a, seg b)
38
39{
40
41 return a.apha < b.apha;
42
43}
44
45int main()
46
47{
48
49 while (scanf("%d", &n) == 1 )
50
51 {
52
53 R = 1;
54
55 if(n == 0 ) break;
56
57 for (int i(0); i < n; i++)
58
59 scanf("%lf %lf", &p[i].x, &p[i].y);
60
61 int cnt = 0;
62
63 int ans = 0, sum = 0;
64
65 point tp;
66
67 double dist, a1, a2;
68
69 for (int i(0); i < n; i++)
70
71 {
72
73 cnt = 0;
74
75 for (int j(0); j < n; j++)
76
77 {
78
79 if (i == j)
80
81 continue;
82
83 tp.x = p[i].x - p[j].x;
84
85 tp.y = p[i].y - p[j].y;
86
87 dist = sqrt(tp.x * tp.x + tp.y * tp.y);
88
89
90
91 if(dist <= 2 * R)
92
93 {
94
95 double ang = atan2(p[j].y - p[i].y, p[j].x - p[i].x);
96
97 if(ang < 0) ang += 2 * pi;
98
99 double tpa = acos(dist / (2 * R));
100
101 a1 = ang + tpa + 2 * pi;
102
103 a2 = ang - tpa + 2 * pi;
104
105 s[cnt].apha = a2, s[cnt].flag = 1;
106
107 cnt++;
108
109 s[cnt].apha = a1, s[cnt].flag = 0;
110
111 cnt++;
112
113 }
114
115 }
116
117 if (ans >= cnt / 2)
118
119 continue;
120
121 sort(s, s + cnt, cmp);
122
123 sum = 0;
124
125 for (int j(0); j < cnt; j++)
126
127 {
128
129 if (s[j].flag) sum ++;
130
131 else sum --;
132
133 if(sum > ans) ans = sum;
134
135 }
136
137 }
138
139 printf("%d\n", ans + 1);
140
141 }
142
143 return 0;
144
145}
146
147
HOJ 2940 Pit Lord 加上了每点的权值，做法类似