返回小组 开始 2020-08-11 14:00:00

NOI 2020云南赛区选拔赛 第二试

结束 2020-08-11 19:00:00
Contest is over.
当前 2024-09-20 00:59:18

C. 几何

描述

给定N个点的坐标(横纵坐标均不小于0),按照横坐标从小到大用折线顺次连接起来,这些折线称为G线,G线上所有点的横坐标均不相同。

请你找一个这样的一个位置:

(1)纵坐标比所有给定点的纵坐标大(可以等于);

(2)纵坐标要尽可能小;

(3)该位置与其他任何一点的连线不能与G线相交(但可以与G线相切);

(4)如果有多个位置满足条件,选择横坐标最小的那个;

(5)你所选择的位置的横坐标要在给定的所有点的横坐标范围内。

输入

输入数据有若干行。

第一行为一个整数N,代表共有N个点。

接下来的N行,每一行有两个整数xi、yi,表示给定点的坐标。

输出

输出数据为一行两个浮点数,表示纵坐标尽可能小的且与其他任何一点的连线均未与G线相交的位置坐标,数据保留两位小数(四舍五入)。

样例

输入

6
2 2
6 1
8 6
10 3
16 5
20 2

输出

9.54 9.85

提示

【样例说明】

15938239299959.png

【数据规模与约定】

40%的数据2≤N≤10、0≤xi,yi≤5*10^6

100%的数据2≤N≤1*106、0≤xi,yi≤5*10^6


Submit

登录

注册
时间限制 2 秒
内存限制 256 MB
提交