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