给定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
【样例说明】
【数据规模与约定】
40%的数据2≤N≤10、0≤xi,yi≤5*10^6
100%的数据2≤N≤1*106、0≤xi,yi≤5*10^6
时间限制 | 2 秒 |
内存限制 | 256 MB |