題目鏈接：http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=27586
題意：
?????? 在海岸線上擺放雷達并限定雷達覆蓋半徑d，再以海岸線為軸，給定海上島嶼坐標，求至少需要多少雷達可以覆蓋所以島嶼，如果不能輸出'-1'。
案例：
??????? Sample Input
??????? 3 2
??????? 1 2
??????? -3 1
?????2 1
?
????????1 2
??????? 0 2
?
??????? 0 0
??????? Sample Output?????
Case 1: 2Case 2: 1 分析：
??????? 可以轉換為區間覆蓋問題。以島嶼為圓心，雷達掃射半徑為半徑，求出此圓與x軸（即海岸線）交點坐標，兩交點坐標間即為雷達擺放區間（包括兩交點（在此區間任意位置擺放雷達均可覆蓋島嶼））。接下來即為區間覆蓋求解問題了。
源代碼：
1 #include<cstdio> 2 #include<cmath> 3 #include<algorithm> 4 using namespace std; 5 int n,num; 6 struct former 7 { 8 double l; 9 double r; 10 }a[1005]; 11 double cmp(former m,former t)//區間排序 12 { 13 if(m.r==t.r) return m.l>t.l; 14 else 15 return m.r<t.r; 16 } 17 void change()//計算所需雷達 18 { 19 int k=0; 20 sort(a,a+n,cmp); 21 for(int j=1;j<n;j++) 22 { 23 if(a[j].l>a[k].r) 24 { 25 num++; 26 k=j; 27 } 28 } 29 } 30 int main() 31 { 32 int cnt=0; 33 double x,y,d; 34 while(scanf("%d%lf",&n,&d)&&n&&d) 35 { 36 num=1; 37 for(int i=0;i<n;i++) 38 { 39 scanf("%lf%lf",&x,&y); 40 if(d<y||d<0)//判斷是否有島嶼超出雷達覆蓋范圍 41 num=-1; 42 a[i].l=x-sqrt(d*d-y*y);//島嶼轉換可擺放雷達區間 43 a[i].r=x+sqrt(d*d-y*y); 44 } 45 if(num==-1) 46 printf("Case %d: -1\n",++cnt); 47 else 48 { 49 change(); 50 printf("Case %d: %d\n",++cnt,num); 51 } 52 } 53 return 0; 54 }
?
)
