Radar Installation
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 107617 | Accepted: 23898 |
Description
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
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
Input
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
The input is terminated by a line containing pair of zeros
Output
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.
Sample Input
3 2 1 2 -3 1 2 1 1 2 0 2 0 0
Sample Output
Case 1: 2 Case 2: 1
Source
使用贪心算法即可得出结论
我们尝试简化问题。
1⃣️当只有一座岛屿时，最优解很明显是一。
2⃣️当有两座岛屿时，雷达放置的位置个岛屿的位置有关，每个岛都对应可以放置雷达的一段范围，若两座岛的范围有重合的地方最优解为一，反之则为二。
3⃣️当岛屿数量较多，我们就可以每次都采取2⃣️中的思路，每次都采取2⃣️中的最优解，逐渐从几百个岛屿简化为几个从而得到答案。
ac代码：可能有些冗长
1 #include<iostream> 2 #include<cmath> 3 #include<algorithm> 4 using namespace std; 5 class point 6 { 7 public: 8 double x; 9 double y; 10 double zuo; 11 double you; 12 }; 13 point p[1001]; 14 int compare1(const point& a,const point& b) 15 { 16 return (a.x<b.x)||((a.x==b.x)&&(a.y<b.y)); 17 } 18 int compare2(const point& a,const point& b) 19 { 20 return a.y>b.y; 21 } 22 int main() 23 { 24 int n,i,j,k=0; 25 double d; 26 while(1) 27 { 28 cin>>n>>d; 29 if(n==0&&d==0)break; 30 k++; 31 for(i=0;i<n;i++) 32 { 33 cin>>p[i].x>>p[i].y; 34 p[i].zuo=p[i].x-sqrt(d*d-p[i].y*p[i].y); 35 p[i].you=p[i].x+sqrt(d*d-p[i].y*p[i].y); 36 } 37 sort(p,p+n,compare2); 38 if(d<p[0].y) 39 { 40 cout<<"Case "<<k<<": "<<-1<<endl; 41 continue; 42 } 43 sort(p,p+n,compare1); 44 double zuo,you; 45 int sum=1,t=1; 46 while(t<n) 47 { 48 zuo=p[t-1].zuo; 49 you=p[t-1].you; 50 while(1) 51 { 52 if(t>n-1) 53 break; 54 if(p[t].zuo>you) 55 { 56 t++; 57 sum++; 58 break; 59 } 60 61 if(p[t].zuo>=zuo&&p[t].zuo<=you&&p[t].you>=you) 62 { 63 zuo=p[t].zuo; 64 t++; 65 } 66 else if(p[t].zuo>=zuo&&p[t].you<=you) 67 { 68 zuo=p[t].zuo; 69 you=p[t].you; 70 t++; 71 } 72 else if(p[t].zuo<=zuo&&p[t].you>=you) 73 { 74 t++; 75 } 76 } 77 } 78 cout<<"Case "<<k<<": "<<sum<<endl; 79 } 80 return 0; 81 }