TopCoder

Thumb fhvirus icon.001
FHVirus
"FHVirus 是一種由主要由IO組合而成的病毒。"

User's AC Ratio

87.5% (7/8)

Submission's AC Ratio

14.7% (10/68)

Tags

Description

和平的時代要結束了!

黑色騎士團又回來了,這次他們進口了一批飛彈發射器,標榜超高破壞力和超遠射程距離,是依照熱狗神─阿思遺留在人間的兵器設計圖研發出來的。
唯一的缺點就是它沒有輪子!依照設計圖做成的熱狗轉輪支持了一秒就爛掉了,所以它的射擊範圍變成只有一條線。
騎士團團長分配每一台發射器幾個預轟炸的城市,希望藉著分工合作,彌補射程範圍的不足。
然而,飛彈是很貴的,所以黑色騎士團希望能用最少的發射次數來達成任務,你能幫他們求出對每一台發射器最少的發射次數是多少嗎?

Input Format

每一組測資代表一個發射器,第一行會有兩個數字n(1≦n≦1000000)和d,n代表有多少個目標城市,d代表每個飛彈的轟炸半徑。
為了方便計算,把發射器的射擊範圍用x軸代替,再給你每個目標城市的相對位置。
接下來有n行,每行兩個數字xi和yi代表該目標的座標。(xi,yi和d皆可用int儲存)

Output Format

請輸出最少需要發射幾次才能轟炸完畢那些城市。

如果無法達成,請輸出-1。

Sample Input

3 2
-1 1
2 2
1 1

Sample Output

2

Hints

範例測資的圖 ( 藍色是飛彈轟炸點,紅色是目標城市 ) :

P.S.原標題:裡x開始x飛彈
P.S.2.原標題可以倒著念

Scoring:

對於 20% 的測試資料,n≦100,d≦1000 。
對於 30% 的測試資料,n≦1000,d≦10000 。

Problem Source

原TIOJ1567 / Problem Setter: poloo5582
(Adapted From: Beijing 2002)

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5
5 1000 65536 262144 6
6 1000 65536 262144 7
7 1000 65536 262144 8
8 1000 65536 262144 9
9 1000 65536 262144 10