大災變

大災變是我在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%的分數。

相關日誌