描述:
假设海岸线是一条无限延伸的直线。它的一侧是陆地,另一侧是海洋。每一座小岛是在海面上的一个点。雷达必须安装在陆地上(包括海岸线),并且每个雷达都有相同的扫描范围d。你的任务是建立尽量少的雷达站,使所有小岛都在扫描范围之内。
数据使用笛卡尔坐标系,定义海岸线为x轴。在x轴上方为海洋,下方为陆地。
样例1如图所示
输入格式:
第一行包括2个整数n和d,n是岛屿数目,d是雷达扫描范围。
接下来n行为岛屿坐标。
输出格式:
一个整数表示最少需要的雷达数目,若不可能覆盖所有岛屿,输出“-1”。
输入样例#1:
3 2
1 2
-3 1
2 1
输出样例#1:
2
这是一道贪心的问题,
因为每一个雷达都有一个覆盖半径,而我们需要将所有的点都覆盖
那么我们是不是可以这样想
因为每一个点都需要被覆盖,所以我们需要让每一个点扩充成一个半径是/雷达可以覆盖的半径/的圆
然后再把每一个圆与x轴的交点坐标算出来
这样我们就成功的把这道题转换成了线段覆盖的问题
再把产生的数据按照末尾的结束顺序排序,再在每一个没有访问过的节点的末尾放置一个雷达即可
参考代码:
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<algorithm>
6 using namespace std;
7 struct node
8 {
9 double x;
10 double y;
11 }a[10001];
12 int n,d;
13 int vis[10001];
14 int ans=0;
15 int comp(const node & a , const node & b)
16 {
17 if(a.y==b.y)return a.x<b.x;
18 else return a.y<b.y;
19 }
20 int main()
21 {
22 scanf("%d%d",&n,&d);
23 for(int i=1;i<=n;i++)
24 {
25 int x,y;
26 scanf("%d%d",&x,&y);
27 if(d<y)
28 {
29 printf("-1");
30 return 0;
31 }
32 double l=sqrt(d*d-y*y);
33 a[i].x=(double)x-l;
34 a[i].y=(double)x+l;
35 }
36 sort(a+1,a+n+1,comp);
37 for(int i=1;i<=n;i++)
38 {
39 if(vis[i]==0)
40 {
41 ans++;
42 for(int j=i;j<=n;j++)
43 if(a[j].x<a[i].y)vis[j]=1;
44 }
45 }
46 printf("%d",ans);
47 return 0;
48 }