大灾变

大灾变是我在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%的分数。

相关日志