2625 雷達安裝

?時間限制: 1 s ?空間限制: 32000 KB ?題目等級 : 黃金 Gold 題目描述?Description

假定海岸線是一條無限延伸的直線，陸地在海岸線的一邊，大海在另一側。海中有許多島嶼，每一個小島我們可以認為是一個點。現在要在海岸線上安裝雷達，雷達的覆蓋范圍是d，也就是說大海中一個小島能被安裝的雷達覆蓋，那么它們之間的距離最大為d。

?

我們使用平面直角坐標系，定義海岸線是x軸，大海在x軸上方，陸地在下方。給你海中每一個島嶼的坐標位置（x,y）和要安裝的雷達所覆蓋的范圍d，你的任務是寫一個程序計算出至少安裝多少個雷達能將所有的島嶼覆蓋。

輸入描述?Input Description

第一行兩個整數n（1≤n≤100000）和d，分別表示海中島嶼的數目和雷達覆蓋的范圍半徑d。

接下來n行，每行兩個整數，表示每個島嶼的坐標位置（x,y）。

輸出描述?Output Description

一行一個整數，即能將所有島嶼全部覆蓋至少安裝的雷達個數，如果無解則輸出“-1”。

樣例輸入?Sample Input 3 2 1 2 -3 1 2 1 樣例輸出?Sample Output

2

數據范圍及提示?Data Size & Hint

（1≤n≤100000）

注意會輸出-1

1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cmath> 5 using namespace std; 6 7 const int N = 100010 ; 8 9 struct node 10 { 11 double begin,end; 12 }lei[N]; 13 14 double now= -20000000.0; 15 int n,m,ans; 16 bool flag=true; 17 18 bool cmp(node a,node b) 19 { 20 return a.end<b.end; 21 } 22 int main() 23 { 24 scanf("%d%d",&n,&m); 25 for(int i=1;i<=n;++i) 26 { 27 double a,b; 28 scanf("%lf%lf",&a,&b); 29 if(b>m)flag=false ; 30 double c=sqrt(m*m-b*b); 31 lei[i].begin=a-c; 32 lei[i].end=a+c; 33 } 34 if(flag==false) 35 { 36 printf("-1"); 37 return 0; 38 } 39 sort(lei+1,lei+n+1,cmp); 40 for(int i=1;i<=n;++i) 41 { 42 if(lei[i].begin>now) now=lei[i].end,ans++; 43 } 44 printf("%d",ans); 45 return 0; 46 }

?

轉載于:https://www.cnblogs.com/mjtcn/p/6815012.html

總結

以上是生活随笔為你收集整理的2625 雷达安装的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。