Radar Installation

Time Limit: 1000MSMemory Limit: 10000K

Total Submissions: 51377Accepted: 11527

  思路  ： 每一个岛都在X轴上有一个区间能够被雷达覆盖，x1为可覆盖的左端点，x2为可覆盖的右端点,x1,x2关于岛的X对称。

先对岛以x排序，然后贪心。

将第一个岛的区间  len[ i ].right与其后的岛与区间len[  k  ].left比假设前者大则继续与后面的比反之则将区间更新到后者的区间范围  此时ans+1（注意假设有岛屿的区间

len [ k ].right<前者的区间  len[ i ].right 则将区间更新到len[ k ].right）  在继续比下去;

总之就是让雷达在满足当前情况的前提下尽量往右方。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;struct Class{    double x;    double y;}zb[1005];struct Std{    double s;    double e;}len[1005];double r;int ans,n;bool cmp(Class a,Class b){    return a.x
          
           >n>>r,n||r) { flag=0; ans=1; for(i=0;i
           
            >zb[i].x>>zb[i].y; for(i=0;i
            
             r) { flag=1; } if(flag) { cout<<"Case "<
             
              <<": "<<"-1"<