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

数据范围及提示 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 }