当前位置:   article > 正文

ACM题解——贪心——卫星安装_贪心算法与卫星结合

贪心算法与卫星结合

ACM题解——贪心——卫星安装转化类似节目安排问题

题目描述

Assume the coasting is an infinite straight line. Land is in one side of coasting, sea in the other. Each small island is a point locating in the sea side. And any radar installation, locating on the coasting, can only cover d distance, so an island in the sea can be covered by a radius installation, if the distance between them is at most d.

We use Cartesian coordinate system, defining the coasting is the x-axis. The sea side is above x-axis, and the land side below. Given the position of each island in the sea, and given the distance of the coverage of the radar installation, your task is to write a program to find the minimal number of radar installations to cover all the islands. Note that the position of an island is represented by its x-y coordinates.
 

  Figure A Sample Input of Radar Installations

 

Input

The input consists of several test cases. The first line of each case contains two integers n (1<=n<=1000) and d, where n is the number of islands in the sea and d is the distance of coverage of the radar installation. This is followed by n lines each containing two integers representing the coordinate of the position of each island. Then a blank line follows to separate the cases.

The input is terminated by a line containing pair of zeros

 

Output

For each test case output one line consisting of the test case number followed by the minimal number of radar installations needed. "-1" installation means no solution for that case.

 

Sample Input

3 2
1 2
-3 1
2 1

1 2
0 2

0 0

Sample Output

Case 1: 2
Case 2: 1

题意

现在有n个点,给定n个位置(xi,yi)(均>=0),有半径为r的卫星安装在x轴上,想要所有卫星的辐射范围囊括所有位置,求最少的卫星个数。

 

题解

一开始我想的是将岛屿按照x轴大小排序,然后for循环遍历,y轴大于半径直接让标记值为1,跳出循环,输出-1;如果不是就让这个点压在一个半圆的最左边,求圆心,以致包括右边更多的点,这个圆心传递下去;遍历第二个坐标依次判断y轴是不是大于半径,然后查看该点坐标在不在以传递圆心为圆心的半圆内,若在传递圆心不变,要不在,就让这个点做新圆心的边界最左,然后求新的圆心值,并且卫星个数++;最后遍历完所有位置,输出卫星个数即可。

但是wa了,以上坐标我虽然都用了double来算,但是不排除有小数取了整造成的偏移错误。于是考虑换一个算法:

对每一个位置,确定可以满足囊括这个位置的圆心范围,x1,x2,   x1=xr2y2    x2=x+r2y2,将每一个位置的圆心范围放入结构体,按照右范围(注意一定是按右范围进行排序)从小到大排序,记录当前右范围curr;循环遍历每一个位置的左右范围,若左范围<=curr,则不做处理,若>curr,则更新curr为当前右范围,且卫星计数器++;最终遍历完所有位置之后输出计数器的值即可。

代码

  1. #include<iostream>
  2. #include<algorithm>
  3. #include<cmath>
  4. using namespace std;
  5. struct point
  6. {
  7. long double x;
  8. long double y;
  9. long double l; //记录岛屿 圆心左范围
  10. long double r; // 圆心右范围
  11. };
  12. bool cmp(point a,point b)
  13. {
  14. return a.r<b.r;
  15. }
  16. int main()
  17. {
  18. int n=0;
  19. double k=0;
  20. cin>>n>>k;
  21. long long int num=0;
  22. while(n!=0 || k!=0)
  23. {
  24. num++;
  25. point *p=new point[n];
  26. bool flag=0;
  27. for(int i=0;i<n;i++)
  28. {
  29. cin>>p[i].x>>p[i].y;
  30. p[i].l=p[i].x-sqrt(k*k-p[i].y*p[i].y);
  31. p[i].r=p[i].x+sqrt(k*k-p[i].y*p[i].y);
  32. if(p[i].y>k)
  33. flag=1;
  34. }
  35. if(flag==1)
  36. cout<<"Case "<<num<<": "<<"-1"<<endl; //先排除有y大于r的可能
  37. else
  38. {
  39. sort(p,p+n,cmp);
  40. long long int coun=1;
  41. long double index=p[0].r;
  42. for(int i=1;i<n;i++)
  43. {
  44. if(p[i].l>index)
  45. {
  46. coun++;
  47. index=p[i].r;
  48. }
  49. }
  50. cout<<"Case "<<num<<": "<<coun<<endl;
  51. }
  52. cin>>n>>k;
  53. }
  54. return 0;
  55. }

 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/很楠不爱3/article/detail/75088
推荐阅读
相关标签
  

闽ICP备14008679号