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
}
?
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
