version 1
从右到左排序，每次都尽可能的选打击范围内最右边的点安装雷达（由于浮点，所以不要一棒子打死的判断是大是小，给出一个精度范围，一开始范围给打了就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
|
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#define MAXN 1005
using namespace std;
struct node
{
double x,y,pos;
node()
{
x = y = pos = -1.0;
}
}per[MAXN];
int n;
double m;
bool cmp(node a,node b)
{
return a.pos< b.pos;
}
bool init()
{
bool flag = true;
for(int i = 1;i <= n;i ++)
{
scanf("%lf %lf",&per[i].x , &per[i].y);
if(per[i].y > m)
flag = false;
per[i].pos = per[i].x + sqrt(m * m - per[i].y * per[i].y);
}
if(!flag)
return false;
sort(per + 1 , per + n + 1 , cmp);
return true;
}
int calc()
{
int cnt = 0,id = 1;
while(id <= n)
{
double now = per[id].pos;
cnt ++;
while(id <= n &&
(fabs(per[id].x - now) * (per[id].x - now) + per[id].y * per[id].y - m * m) <= 0.001)
{
id ++;
}
}
return cnt ;
}
int main()
{
int cnt = 1;
while(cin>>n>>m && (n || m))
{
if(!init())
{
printf("Case %d: -1\n",cnt);
cnt ++;
continue;
}
printf("Case %d: %d\n",cnt , calc());
cnt ++;
}
return 0;
}
|
version 2
找到以每个岛为圆心的圆与x轴左右交点形成一个区间，按左端点关键字升序排序后，用右端点去覆盖之后的点（如果遇到更小的右端点应该把目前的点更新），遇到不能覆盖的就雷达数目+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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
|
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#define MAXN 1005
using namespace std;
struct node
{
double x,y,lp,rp;
node()
{
x = y = lp = rp = -1.0;
}
}per[MAXN];
int n;
double m;
bool cmp(node a,node b)
{
return a.lp < b.lp;
}
bool init()
{
bool flag = true;
for(int i = 1;i <= n;i ++)
{
scanf("%lf %lf",&per[i].x , &per[i].y);
if(per[i].y > m)
flag = false;
per[i].lp = per[i].x - sqrt(m * m - per[i].y * per[i].y);
per[i].rp = per[i].x + sqrt(m * m - per[i].y * per[i].y);
}
if(!flag)
return false;
sort(per + 1 , per + n + 1 , cmp);
return true;
}
int calc()
{
int cnt = 1,id = 1;
bool mark[MAXN] = {false};
double now = per[1].rp;
for(int i = 1;i <= n;i ++)
{
if(per[i].rp < now)
now = per[i].rp;
if(per[i].lp > now)
{
cnt ++;
now = per[i].rp;
}
}
return cnt;
}
int main()
{
int cnt = 1;
while(cin>>n>>m && (n || m))
{
if(!init())
{
printf("Case %d: -1\n",cnt);
cnt ++;
continue;
}
printf("Case %d: %d\n",cnt , calc());
cnt ++;
}
return 0;
}
|