本文正體字版由OpenCC轉換
大災變是我在2009年末的時候在NOI國家集訓隊冬令營出的題，題目背景是魔獸世界。當年出題的時候剛好聽到魔獸世界第三個資料片「大災變」的傳聞，所以就以此爲背景了，之前我還出過三次魔獸世界模擬賽的題。今天回頭重新來看，發現題解和數據的質量還是很高的，所以決定發佈出來。有趣的是，我還給題解的每個算法起了一個名字，如下表所示：
| 思路甲 | 欲窮千里目，更上一層樓 | 說明“站得越高，看得越遠”的道理 |
| 算法一 | 行遠必自邇，登高必自卑 | 太高了要降低高度，說明二分的原理 |
| 思路乙 | 不識廬山眞面目，祇緣身在此山中 | 說明可視區域在山脈上方 |
| 算法二 | 表獨立兮山之上，雲容容兮而在下 | 在山脈上空的下凸線上掃描最低點，比喻爲雲層 |
| 算法三 | 刪繁就簡三秋樹，領異標新二月花 | 用“刪繁就簡”概括維護凸線的堆棧（單調隊列） |
| 算法四 | 近水樓臺先得月，向陽花木易逢春 | 比喻製造單調性的優勢 |
| 思路丙 | 會當淩絕頂，一覽眾山小 | 猜想到山坡交線最高點就能看見山脈 |
| 算法五 | 不畏浮雲遮望眼，自緣身在最高層 | 在上升線和下降線的最高點，就能一覽山脈全貌 |
資源鏈接
問題描述
艾澤拉斯世界經歷一場亙古未有的地震過後，大地和海洋被完全撕裂，舊大陸殘缺不全。聯盟和部落各種族的居民們被迫離開了世代居住的家園，來尋找新的生存空間。原本平坦的陸地上現在隆起了一座座山峯，暴風城的人類開始在艾爾文山脈重建家園。他們決定在山脈之中建造一座瞭望塔和一個魔法浮空島，以便於在瞭望塔和浮空島上可以俯視艾爾文山脈的全貌。
艾爾文山脈被描述爲一個折線，給定每個點的座標（橫縱座標均不小於0），按照橫座標從小到大順次連接起來就是就是山脈的折線。折線上所有點的橫座標均不相同。如果一個位置與山脈任何一點的連線均不被擋住（但可以與地面相切），那麼就說這一點可以望到整個艾爾文山脈。瞭望塔的塔身不會擋住視線，而且瞭望塔和浮空島可以建造在同一位置。爲節省建築材料，瞭望塔塔身的高度必須儘量小，即從塔頂到塔底的距離儘量小，瞭望塔可以建在山坡上。由於氣候因素，浮空島應建立在海拔儘量低的位置（甚至可以建在地面上），海平面高度爲0。如果有多個位置均滿足條件，則選擇橫座標最小的那個。瞭望塔和浮空島橫座標範圍應在艾爾文山脈橫座標範圍之內。給定艾爾文山脈，請你求出瞭望塔和浮空島的位置。
輸入文件
- 第
1行，一個整數N，表示描述艾爾文山脈的折線的頂點數。 - 第
2-N+1行，每行兩個整數，xi, yi表示折線上點的座標。
輸出文件
- 第1行，兩個保留3位小數的浮點數
x1, y1，表示瞭望塔頂端的座標。 - 第2行，兩個保留3位小數的浮點數
x2, y2，表示浮空島的座標。
輸入樣例
6
2 2
6 1
8 6
10 3
16 5
20 2
輸出樣例
8.00 11.00
9.54 9.85
樣例說明
樣例中描述的艾爾文山脈各個頂點，按照橫座標順序順次連接後的折線如下圖所示：
瞭望塔應建造在山峯(8, 6)處，塔頂端爲(8, 11)，高度爲5，此時瞭望塔的高度最小。
浮空島建立在(9.54, 9.85)處，海拔高度最低。
問題限制
- 時間限制2000 ms
- 內存限制128 MB
數據規模
- 40%的數據2<=N<=10
- 100%的數據2<=N<=1 000 000；0<=xi,yi<=5 000 000
評分方式
對於每個測試點，如果輸出的結果與答案文件完全相同，得該測試點100%的分數，如果僅有一行與答案文件相同，得該測試點50%的分數，否則得0%的分數。
上次修改時間 2017-05-17