贪心算法

Assume the coasting is an infinite straight line. Land is in one side of coasting, sea in the other. Each small island is a point locating in the sea side. And any radar installation, locating on the coasting, can only cover d distance, so an island in the sea can be covered by a radius installation, if the distance between them is at most d. 

We use Cartesian coordinate system, defining the coasting is the x-axis. The sea side is above x-axis, and the land side below. Given the position of each island in the sea, and given the distance of the coverage of the radar installation, your task is to write a program to find the minimal number of radar installations to cover all the islands. Note that the position of an island is represented by its x-y coordinates. 
 
Figure A Sample Input of Radar Installations

The input consists of several test cases. The first line of each case contains two integers n (1<=n<=1000) and d, where n is the number of islands in the sea and d is the distance of coverage of the radar installation. This is followed by n lines each containing two integers representing the coordinate of the position of each island. Then a blank line follows to separate the cases. 

The input is terminated by a line containing pair of zeros 

For each test case output one line consisting of the test case number followed by the minimal number of radar installations needed. "-1" installation means no solution for that case.

 

 

判断需要建造最少的雷达时，需要将远的

 

1. #include <iostream>  
2. #include <algorithm>  
3. #include <stdlib.h>  
4. #include <math.h>  
5.   
6. using namespace std;  
7.   
8. struct point  
9. {  
10.     double left, right;  
11. }p[2010], temp;  
12.   
13. bool operator < (point a, point b)  
14. {  
15.     return a.left < b.left;  
16. }  
17.   
18. int main()  
19. {  
20.     int n;  
21.     double r;  
22.     int kase = 0;  
23.     while (cin >> n >> r && (n || r))  
24.     {  
25.         bool flag = false;  
26.         for (int i = 0; i < n; i++)  
27.         {  
28.             double a, b;  
29.             cin >> a >> b;  
30.             if (fabs(b) > r)  
31.             {  
32.                 flag = true;  
33.             }  
34.             else  
35.             {  
36.                 p[i].left = a * 1.0 - sqrt(r * r - b * b);  
37.                 p[i].right = a * 1.0 + sqrt(r * r - b * b);  
38.             }  
39.         }  
40.         cout << "Case " << ++kase << ": ";  
41.         if (flag)  
42.         {  
43.             cout << -1 << endl;  
44.         }  
45.         else  
46.         {  
47.             int countt = 1;  
48.             sort(p, p + n);  
49.             temp = p[0];  
50.               
51.             for (int i = 1; i < n; i++)  
52.             {  
53.                 if (p[i].left > temp.right)  
54.                 {  
55.                     countt++;  
56.                     temp = p[i];  
57.                 }  
58.                 else if (p[i].right < temp.right)  
59.                 {  
60.                     temp = p[i];  
61.                 }  
62.             }  
63.             cout << countt << endl;  
64.         }  
65.     }  
66. }  

至今不懂