http://poj.org/problem?id=1328
题的大意就是说在海里有小岛，坐标位置会给出，需要岸边的雷达覆盖所有的小岛，但雷达的覆盖范围有限，所以，需要最少的雷达覆盖所有的小岛，但若是有小岛没法被雷达给覆盖到，就输出-1；
这个题的话可以转化成区间问题就是看雷达的覆盖范围作为半径，A若是小岛的位置，根据雷达的覆盖范围只要不小于这个点的Y坐标，那个覆盖范围就是这个三角形的斜边，所以只要雷达位于1,2边上就可以覆盖到这个小岛
1
#include<cstdio>
2
#include<cstring>
3
#include<iostream>
4
#include<cstdlib>
5
#include<cmath>
6
#include<algorithm>
7
using
namespace
std ;
8
struct
node
9
{
10
double
x,y;
11
} s[
10001
];
12
int
cmp(
struct
node a,
struct
node b)
13
{
14
if
(a.y<
b.y)
15
return
1
;
16
else
return
0
;
17
}
18
int
main()
19
{
20
int
n,d ;
21
int
cnt =
1
;
22
while
(cin>>n>>
d)
23
{
24
25
int
flag =
0
;
26
if
(n ==
0
&&d ==
0
)
break
;
27
double
a,b ;
28
for
(
int
i =
1
; i <= n ; i++
)
29
{
30
scanf(
"
%lf %lf
"
,&a,&
b);
31
if
(fabs(b) >
d)
32
flag =
1
;
33
s[i].x = a-sqrt(d*d-b*
b);
34
s[i].y = a+sqrt(d*d-b*
b);
35
}
36
cout<<
"
Case
"
<<
'
'
<<cnt<<
'
:
'
<<
'
'
;
37
if
(flag ==
1
)
38
cout<<
"
-1
"
<<
endl ;
39
else
40
{
41
sort(s+
1
,s+
1
+
n,cmp);
42
int
sum =
1
;
43
double
zhizhen = s[
1
].y;
44
for
(
int
i =
2
; i <= n ; i++
)
45
{
46
if
(s[i].x>
zhizhen)
47
{
48
sum++
;
49
zhizhen =
s[i].y;
50
}
51
}
52
53
cout<<sum<<
endl;
54
}
55
cnt++
;
56
}
57
return
0
;
58
}
