| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 96747 | Accepted: 21508 |
Description
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 is terminated by a line containing pair of zeros
Output
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
题意分析
给定一个直角坐标系，定义x轴为海岸线，海岸线上方是海，下方是陆地.
在海域零星分布一些海岛, 需要要在海岸线上安装若干个雷达覆盖这些海岛,
每个雷达的覆盖半径都是相同且固定的.
现在给定所有海岛的坐标(x,y), 以及雷达的覆盖半径d，
问可以覆盖所有海岛的最小雷达数.
解题思路：
无解的情况：
y>d或者是y<0或是d<0
有解的情况：
以海岛坐标(x,y)为圆心，用雷达覆盖半径d画圆，根据前提条件可知，
这个圆与x轴必定存在最少1个(y=d)、最多2个交点(y<d).
可以认为1个交点是2个交点重合的特殊情况，那么这2个交点在x轴上构成的线性区间，
可以看作海岛的被覆盖范围在x轴上的投影 (由此就可以把二维的几何问题转化成一维几何问题)
按照所有海岛的x轴坐标，从小到大依次计算每个海岛在x轴上的投影区间（投影可能存在重叠），
同时把每个雷达抽象成1个点，那么此问题就转化成：
【已知x轴上若干个区间（可能存在交集），现在要往这些区间内放若干个点，
问怎样放置这些点，使得每个区间内至少存在一个点，且所放置的点的总量尽可能最少】
可使用贪心算法求解：
根据每个区间的左端点坐标对所有区间从左到右排序:
① 在左起第一个区间A 的右端点 A.R 放置一个点，总放置点数 P+1
② 若下一个区间B 的左端点 B.L > A.R,
说明 区间A 与 区间B 无交集，此时在区间B 的右端点 B.R 放置一个点，总放置点数 P+1
否则说明 区间A 与 区间B 相交, 此时进一步判断，若 B.R < A.R，
说明 区间B 在 区间A 的内部，此时把原本放置在 A.R 的点移动到 B.R（确保区间B有一个点），总放置点数不变
③ 重复这个过程直到所有区间被遍历完成
测试样例： 3 2 1 0 -3 -1 2 1 2 2 1 1 2 2 5 4 -2 2 1 2 0 3 3 3 4 3 9 3 0 2 -3 2 -4 2 -5 2 3 2 6 2 9 2 12 2 15 2 3 2 1 2 -3 1 2 1 1 2 0 2 0 0
1 #include<iostream> 2 #include<math.h> 3 #include<algorithm> 4 using namespace std; 5 struct seaside{ 6 double left; 7 double right; 8 }; 9 bool compare(seaside a,seaside b) 10 { 11 return a.left<=b.left; 12 } 13 int solve(seaside *a,int n) 14 { 15 ///进行排序 16 sort(a,a+n,compare); 17 double fright; 18 fright = a[0].right; 19 int sum = 1; 20 for(int i=1;i<n;i++) 21 { 22 if(a[i].left > fright) 23 { 24 sum++; 25 fright = a[i].right; 26 }else{ 27 if(a[i].right < fright) 28 { 29 fright = a[i].right; 30 } 31 } 32 } 33 return sum; 34 } 35 int main() 36 { 37 int n; 38 double d; 39 int Count = 1; 40 bool isSolved = 1; 41 cin>>n>>d; 42 while(n!=0) 43 { 44 isSolved = 1; 45 seaside *island = new seaside[n]; 46 double x,y; 47 for(int i=0;i<n;i++) 48 { 49 cin>>x>>y; 50 if(y>d || y<0 || d<0)//无解 51 isSolved = 0; 52 else{ 53 double offset = sqrt(d*d - y*y); // 勾股定理 54 island[i].left = x-offset; 55 island[i].right = x+offset; 56 } 57 58 } 59 60 ///解决问题 61 cout<<"Case "<<Count<<": "; 62 if(isSolved) 63 cout<<solve(island,n)<<endl; 64 else 65 cout<<-1<<endl; 66 67 delete[] island; 68 Count++; 69 cin>>n>>d; 70 } 71 return 0; 72 }
结果： 3 2 1 0 -3 -1 2 1 Case 1: -1 2 2 1 1 2 2 Case 2: 1 5 4 -2 2 1 2 0 3 3 3 4 3 Case 3: 1 9 3 0 2 -3 2 -4 2 -5 2 3 2 6 2 9 2 12 2 15 2 Case 4: 4 3 2 1 2 -3 1 2 1 Case 5: 2 1 2 0 2 Case 6: 1 0 0 Process returned 0 (0x0) execution time : 1.058 s Press any key to continue.