PKU1328-Radar Installation

題目：http://poj.org/problem?id=1328
現在二維平面上有n(1000)個點，想要在x軸上安排針測距離d的雷達、覆蓋所有點
問最少要安排幾個雷達？
(debug搞了N久才發現我Case的C沒大寫…)


程式碼：http://codepad.org/cY2sB3AB
題目簡單啟示卻很大的一道貪心題
首先、答案的可能域只能在一條線上而以
根據本題的條件，很容易把所有的「二維資訊」投影到軸上變成「一維資訊」
也就是針對每一個點，根據座標計算出[p,q]區間表示x軸上此區間至少要裝一個雷達

於是問題轉化成了：有n條區間，安排盡量少的點、讓每一條區間內至少包含一個點
(或者是活動選擇問題：n個活動有開始時間和結束時間，問最多能參加幾個活動互不衝突)

具體的貪心是把計算好的區間們按q排序，依次考慮區間
如果沒被選到的話，那就選定此區間的q作為雷達的設置點
由於考慮的區間會是沒被覆蓋中q在最左邊的，因此選擇比q更小的點不可能更好

似乎需要注意d<=0的情形，總複雜度O(nlgn)