思路在代码的注释中

1 ///2014.3.1 - 2014.3.2 2 ///poj1328 3  4 /** 5  *对要扫描到的每个岛求出雷达可以安置在海岸上的区间[begin,end]， 6  *对这些区间按begin从小到大排序 7  *从第一个区间的end点开始安置雷达，然后依次检索下一个区间， 8  *若下一个区间完全在刚刚安置雷达的区间内（new.begin>=pre.begin && 9  * new.end<=pre.end ),则将刚刚安置的雷达重新安置在这个区间（new）的右端；10  *若下一个区间的左端点在刚刚安置雷达的区间内，而右端点在刚刚安置雷达的11  *区间右侧，则可忽略这个区间向下进行；12  *若下一个区间与刚刚安置雷达的区间完全不相交，则在这个新区间右端内安置13  *一个新雷达。14  */15 16 #include 
     
      17 #include 
      
       18 #include 
       
        19 20 struct Section21 {22     double begin;23     double end;24 };25 bool mycmp(Section a,Section b)26 {27     return a.begin < b.begin;28 }29 30 int n; ///记录区间（小岛）的数目31 int d; ///记录雷达的扫描半径32 Section section[1010]; ///存储每个小岛需要的雷达区间33 34 bool init( )35 {36     bool legalData = true;37     int x,y;38     for(int i=0 ; i
        
         d )43             legalData = false;44     }45     std::sort(section,section+n,mycmp);46     return legalData;47 }48 49 int main( )50 {51 //    freopen("in","r",stdin);52 //    freopen("out","w",stdout);53 54     int cas = 1;55     while( scanf("%d%d",&n,&d)!=EOF && (n || d) ){56         if( !init() ){57             printf("Case %d: -1\n",cas);58             cas++;59             continue;60         }61         if( n==1 ){62             printf("Case %d: 1\n",cas);63             cas++;64             continue;65         }66 67         double pre = section[0].end;68         Section* now;69         int num = 1;70         for(int i=1 ; i
         
          begin > pre ){73                 num++;74                 pre = now->end;75             }76             else if( now->end < pre ){77                 pre = now->end;78             }79         }80 81         printf("Case %d: %d\n",cas,num);82         cas++;83      }84      return 0;85 }