题目：x轴上方有n个目标点，坐标全为整数，为了扫描到他们，在x轴上安放雷达，每一个雷达扫描半径为d，问至少安放多少雷达。

思路：首先，以每个岛为圆心，画出一个圆，应该与x轴有1或2个交点（否则直接输出不可能了）。

这样，n个点就有n个区间，我们以右端点作为排序键，进行排序。维护一个当前区间最小的右端点，当一个新的区间拿来比较的时候 ，若新区间的左端点小于维护的最小右端点，这说明这个新区间所代表的岛可以被旧雷达所扫到，不做动作，而假如新区间的左端点大于当前区间的右端点，说明要新雷达了，雷达数+1，并且新区间变为当前区间，其右端点为当前区间最小右端点。

1. #include<iostream> 
2. #include<cmath> 
3. #include<algorithm> 
4. using namespace std; 
5.  
6. const int island_max=1000; 
7.  
8. class Node 
9. { 
10. public: 
11.    float x; 
12.    float y; 
13. }; 
14.  
15. class Region 
16. { 
17. public: 
18.    float left; 
19.    float right; 
20. }; 
21.  
22. Node island[island_max]; 
23. Region island_re[island_max]; 
24.  
25. bool cmp(Region a,Region b) 
26. { 
27.    return a.right<b.right; 
28. } 
29. int main() 
30. { 
31.     
32.     int num; 
33.     float rad; 
34.      
35.     for(;;) 
36.     { 
37.       //**********输入每个点的坐标，并判断是否有解*****  
38.        cin>>num>>rad; 
39.        if(!(num&&rad)) 
40.           break; 
41.        bool flag = false;  
42.        static int count = 1; 
43.        for(int i=0;i<num;i++) 
44.        { 
45.           Node temp; 
46.           cin>>temp.x>>temp.y; 
47.           island[i]=temp; 
48.           if(island[i].y>rad) 
49.              flag  = true; 
50.        } 
51.         
52.   
53.  
54.        if(flag) 
55.        { 
56.            cout<<"Case "<<count++<<": -1"<<endl; 
57.            continue; 
58.        } 
59.  
60.       /*************算出每个点的区间 ******/ 
61.        
62.    
63.        
64.       for(int i=0;i<num;i++) 
65.       { 
66.          island_re[i].left = island[i].x-sqrt(rad*rad-island[i].y*island[i].y); 
67.          island_re[i].right = island[i].x+sqrt(rad*rad-island[i].y*island[i].y); 
68.          
69.       }  
70.    
71.  
72.       sort(island_re,island_re+num,cmp); //根据交点的右坐标进行排序  
73.        
74.    
75.       /***********根据每个区间算情况********/ 
76.        
77.       int radar = 1; 
78.       float tmp; 
79.       int i; 
80.        
81.        
82.       for(i = 0,tmp = island_re[0].right;i<num-1;i++) 
83.       { 
84.         if(island_re[i+1].left>tmp) 
85.            { 
86.               radar++; 
87.               tmp = island_re[i+1].right; 
88.            } 
89.       } 
90.        
91.       cout<<"Case "<<count++<<": "<<radar<<endl; 
92.    } 
93.    system("pause"); 
94.    return 0; 
95. } 
96.        
97.