1567 . 黑色騎士團的飛彈野望
TopCoder
Tags
Description
和平的時代要結束了！
黑色騎士團又回來了，這次他們進口了一批飛彈發射器，標榜超高破壞力和超遠射程距離，是依照熱狗神─阿思遺留在人間的兵器設計圖研發出來的。
唯一的缺點就是它沒有輪子！依照設計圖做成的熱狗轉輪支持了一秒就爛掉了，所以它的射擊範圍變成只有一條線。
騎士團團長分配每一台發射器幾個預轟炸的城市，希望藉著分工合作，彌補射程範圍的不足。
然而，飛彈是很貴的，所以黑色騎士團希望能用最少的發射次數來達成任務，你能幫他們求出對每一台發射器最少的發射次數是多少嗎？
Input Format
每一組測資代表一個發射器，第一行會有兩個數字n(1≦n≦1000000)和d，n代表有多少個目標城市，d代表每個飛彈的轟炸半徑。
為了方便計算，把發射器的射擊範圍用x軸代替，再給你每個目標城市的相對位置。
接下來有n行，每行兩個數字xi和yi代表該目標的座標。(xi,yi和d皆可用int儲存)
Output Format
請輸出最少需要發射幾次才能轟炸完畢那些城市。
如果無法達成，請輸出-1。
Sample Input 1
3 2
-1 1
2 2
1 1
-1 1
2 2
1 1
Sample Output 1
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 |