网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
大灾变
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | cataclysm.in | 输出文件 | cataclysm.out |
问题描述
艾泽拉斯世界经历一场亘古未有的地震过后,大地和海洋被完全撕裂,旧大陆残缺不全。联盟和部落各种族的居民们被迫离开了世代居住的家园,来寻找新的生存空间。原本平坦的陆地上现在隆起了一座座山峰,暴风城的人类开始在艾尔文山脉重建家园。他们决定在山脉之中建造一座瞭望塔和一个魔法浮空岛,以便于在瞭望塔和浮空岛上可以俯视艾尔文山脉的全貌。
艾尔文山脉被描述为一个折线,给定每个点的坐标(横纵坐标均不小于0),按照横坐标从小到大顺次连接起来就是就是山脉的折线。折线上所有点的横坐标均不相同。如果一个位置与山脉任何一点的连线均不被挡住(但可以与地面相切),那么就说这一点可以望到整个艾尔文山脉。瞭望塔的塔身不会挡住视线,而且瞭望塔和浮空岛可以建造在同一位置。为节省建筑材料,瞭望塔塔身的高度必须尽量小,即从塔顶到塔底的距离尽量小,瞭望塔可以建在山坡上。由于气候因素,浮空岛应建立在海拔尽量低的位置(甚至可以建在地面上),海平面高度为0。如果有多个位置均满足条件,则选择横坐标最小的那个。瞭望塔和浮空岛横坐标范围应在艾尔文山脉横坐标范围之内。给定艾尔文山脉,请你求出瞭望塔和浮空岛的位置。
输入文件
文件名cataclysm.in
第1行,一个整数N,表示描述艾尔文山脉的折线的顶点数。
第2-N+1行,每行两个整数,xi,yi表示折线上点的坐标。
输出文件
文件名cataclysm.out
第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)处,海拔高度最低。
问题限制
数据规模
40%的数据2<=N<=10
100%的数据2<=N<=1 000 000;0<=xi,yi<=5 000 000