[程式設計解題] 天際線資料群

簡介

天際線群這個題目，是第52次ITSA全國線上程式設計月賽的一個題目。題目還算簡單，但麻煩的就在「天際線」的定義不容易理解，理解了後，其實程式是蠻容易寫出來的。

那麼就來看看什麼是天際線吧！

一個資料若是被稱為天際線上的話，表示沒有任何資可以「取代」它。簡單吧！

屁啦，我完全聽不懂！

這很合理，因為我們沒說明什麼叫「取代」。

要說明取代，用圖示的方式最容易啦。我們以 (31，55) 這個資料點為例。所有落於 (31，55)以及 (0，0) 所形成的區間中的點，都會被 (31，55) 取代。白話來說，所有落於下圖「藍色」區塊中的點，都會被 (31，55)取代。例如 (22，32)，(31，22)都被(31，55)取代啦。但因為 (69, 12) 沒有落在圖中藍色的矩形中，所以(69，12) 沒有被(31，55)取代。

注意，注意！有一個例外！

(31，55) 不能取代 (31，55)！（自己不能取代自己囉）

取代的程式碼？

給一個資料點 (a, b)，怎麼判斷它有沒有被(31，55) 取代呢？底下是示範的程式碼。

題目

知道這些後，先來看看題目吧！

詳細題目請點選這裏下載，解壓縮密碼為vtpd2kuwq9

解題步驟

那麼解題的思考步驟如何？

1. 先思考要怎麼儲存資料
2. 思考這個題目的「最簡化」的版本是怎樣？
3. 擴充前述的最簡化版，讓它可以解決整個題目

那一步一步來吧！

如何儲存資料

上圖是資料輸入的格式，可以看出會輸入一群的2維資料。那麼比較適合儲存資料的方式就是2維的 vector 囉。透過底下的方式，就可以把資料讀入啦。

最簡化的版本

最簡化的版本就是，給你一筆資料，假設資料是(31，55)好了，判斷它是不是被排除了。寫成函式的話，就是如下所示啦：

擴充最簡化的版本

知道如何判斷一筆資料是否被排除，那現在你有 n 筆資料，那該怎麼辦？

我想大家都會了，就寫一個迴圈，走訪 buf 中的每個元素。每走訪一個元素，就呼叫上一節寫好的函式，就ok囉。

這部分很簡單，就不寫出來了！