題目鏈接：http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=27586

題意：

?????? 在海岸線(xiàn)上擺放雷達(dá)并限定雷達(dá)覆蓋半徑d，再以海岸線(xiàn)為軸，給定海上島嶼坐標(biāo)，求至少需要多少雷達(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

分析：

??????? 可以轉(zhuǎn)換為區(qū)間覆蓋問(wèn)題。以島嶼為圓心，雷達(dá)掃射半徑為半徑，求出此圓與x軸（即海岸線(xiàn)）交點(diǎn)坐標(biāo)，兩交點(diǎn)坐標(biāo)間即為雷達(dá)擺放區(qū)間（包括兩交點(diǎn)（在此區(qū)間任意位置擺放雷達(dá)均可覆蓋島嶼））。接下來(lái)即為區(qū)間覆蓋求解問(wèn)題了。

源代碼：

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)//區(qū)間排序 12 { 13 if(m.r==t.r) return m.l>t.l; 14 else 15 return m.r<t.r; 16 } 17 void change()//計(jì)算所需雷達(dá) 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)//判斷是否有島嶼超出雷達(dá)覆蓋范圍 41 num=-1; 42 a[i].l=x-sqrt(d*d-y*y);//島嶼轉(zhuǎn)換可擺放雷達(dá)區(qū)間 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 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/huaszjh/p/4719074.html

總結(jié)

以上是生活随笔為你收集整理的Radar Installation的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。