POJ 1328 Radar Installation-白红宇

POJ 1328 Radar Installation

阅读量：5061 次

发布时间：2019-06-12

本文共 1449 字，大约阅读时间需要 4 分钟。

题意：在一片海上有一堆岛，设海岸线为x轴，海为第一二象限，在x轴上可以放置雷达，每个雷达的作用范围是一个半径为d的圆，问最少放几个雷达能把所有岛都包含。

解法：贪心。一开始的想法是把岛按横坐标排序，枚举正好在雷达作用圆的边界上的岛对应的雷达坐标，选择能够覆盖这个岛之前所有的岛的点，并且把所有能覆盖的岛标记。但是不知道为啥就wa了……可能是精度问题……也可能是想错了orz。后来看了一下题解，这个问题可以转化为区间覆盖问题，以每个岛为圆心画一个半径为d圆，与x轴能产生两个交点，表示雷达放在该区间内就能覆盖这个岛，所以只要将区间按左边界排序，贪心的求有公共区间的区间集的最小个数就可以了（自以为机智的处理了精度……然后就wa了）。

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #define LL long longusing namespace std;const double eps = 1e-9;struct node{ int x, y; bool operator < (const node &tmp) const { return x < tmp.x; }}p[1005];struct node1{ double l, r; bool operator < (const node1 &tmp) const { return l < tmp.l; }}q[1005];int main(){ int n, d; int cse = 1; while(~scanf("%d%d", &n, &d) && (n + d)) { int flag = 0; for(int i = 0; i < n; i++) { scanf("%d%d", &p[i].x, &p[i].y); if(p[i].y > d) flag = 1; else { double tmp = sqrt((double)d * d - p[i].y * p[i].y); q[i].l = (double)p[i].x - tmp; q[i].r = (double)p[i].x + tmp; } } printf("Case %d: ", cse++); if(flag) { printf("-1\n"); continue; } sort(q, q + n); int ans = 1; double tmp = q[0].r; for(int i = 1; i < n; i++) { if(q[i].l > tmp)//更新左边界 { ans++; tmp = q[i].r; } else if(q[i].r < tmp)//更新右边界 tmp = q[i].r; } printf("%d\n", ans); } return 0;}

转载于:https://www.cnblogs.com/Apro/p/4498529.html

你可能感兴趣的文章