n113. 無線基地台
Tags :
Accepted rate : 2人/3人 ( 67% ) [非即時]
評分方式:
Tolerant

最近更新 : 2024-01-30 13:34

Content

天龍國有 N 個離岸島嶼,今欲架設沿岸的無線基地台覆蓋這些島嶼,基地台型號為WP1450A,覆蓋範圍為半徑 R 的圓(包含圓周);若海岸線為一水平線(可視為水平 x 坐標軸),每個離岸島嶼 i 有座標 xi、yi ,為了節省經費,國王希望以最少的基地台數覆蓋所有可以覆蓋的島嶼,作為總工程師的你,請設法解決此一難題。

必須注意的是基於某種原因,基地台只能架設在整數 x 座標點上。

<例>

Input

多筆測資(<=100筆),每筆測資第一行兩個整數 N、R,接著會有 N 行,每行兩個浮點數 xi、yi,代表第 i 個島嶼的座標 (其中 yi > 0)。
(R, xi, yi <10^9 , 實際測資之間沒有空行)

Output

每筆測資一行輸出兩個整數 A、B,其中A為最少的基地台數量,B為無法覆蓋的島嶼數量。

Sample Input #1
4 2
-2.5 1
-1.5 2
0 2
0.5 1

8 2
-3 1.5
-2 2.5
-1.5 0.5
-1 1
0.5 2
1 4
2 2
3 0.5
Sample Output #1
2 1
2 3
測資資訊:
記憶體限制: 256 MB
公開 測資點#0 (14%): 1.0s , <1K
公開 測資點#1 (14%): 1.0s , <1M
公開 測資點#2 (14%): 1.0s , <1M
公開 測資點#3 (14%): 1.0s , <1M
公開 測資點#4 (14%): 1.0s , <1M
公開 測資點#5 (15%): 1.0s , <1M
公開 測資點#6 (15%): 1.0s , <1M
Hint :
Tags:
出處:
林口高中練習題 [管理者: hshua (hshua) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」