uva--10382Watering Grass+贪心

题意：

一片长为L宽为W的矩形草坪，然后给出n个喷头的圆心坐标和半径，问你最少需要几个喷头可以覆盖整个草坪。

思路：

刚开始的时候直接觉得可以算出每个喷头可以覆盖的区间，然后就变成前面刚做过的区间覆盖问题了;后面看了一下样例，发现这样想是不对的，因为喷头边沿的圆弧可能是不能完全覆盖住草地的，所以那些地方就必须还要别的喷头去覆盖，这样就不能直接用区间合并来做了。后面又想了一下，其实每个喷头覆盖的有效区域就是一个矩形，我们只需要求出每个喷头覆盖的有效区域（就是矩形完全包含在圆内的部分，用简单的几何知识算一下就可以得到的），就又变成区间覆盖问题了！有一点需要注意：如果一个喷头的半径不大于矩形宽度一半的话，那么这个喷头可以覆盖的有效区域为0（相当于这个矩形的内接圆）,我们可以忽略这些喷头。

代码如下：

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        using namespace std; typedef struct { double x,y; }P; P p[11000]; int cmp(P p1,P p2) { return p1.x
       
        max1) max1=p[i].y; i++; } if(max1==0) break; cnt++; left=max1; if(left>=len) { flag=1; break; } } if(flag) printf("%d\n",cnt); else printf("-1\n"); } return 0; }