2283. Day9 Ex - ▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼▼

そっか、一個思い出した。君は助けない(▼w▼)——はろける《キャンディークッキーチョコレート》

你是一名歌者,现在和你超级超级超级讨厌的青梅竹马 01 开了一家三星级餐厅。01 出差去隔壁某个星球种苹果树了,似乎要离开至少 240 天,而你被她指派去给餐厅进货。看着列满各种巧克力、曲奇、糖还有大葱的进货单,你忽然发现,列表里竟然没有法棍面包。于是为了增加你买法棍面包、摸鱼、去教堂祈祷以及顺便抓个勇者吃的时间,你决定规划一下最合适的进货路径。

你所在的街区可以看作一个网格图。需要去进货的共有 n 个商店,分别位于坐标 p_i = (x_i, y_i)(1 \le i \le n)。你现在决定先选中一个坐标,每次去其中一家商店进货后运到该位置,为了增加摸鱼时间,选中的坐标到所有商店的最大距离应该最小。

即,找到一个坐标,使其到所有给定的 n 个坐标的最大欧氏距离最小。

输入

第一行输入一个整数 n(1 \le n \le 10^5)

接下来 n 行每行输入两个整数 (x_i, y_i)(0 \le |x_i|, |y_i| \le 10^9) 表示坐标。

输出

输出一行两个浮点数表示选中的答案坐标。

设参考答案坐标为 p_0,当你的答案和参考答案距离不超过 \max(10^{-3}, \frac{\max{|p_i - p_0|}}{10^6}) 时视为正确。

样例

标准输入 复制文本
4
0 -1
1 -1
0 0
2 1
标准输出 复制文本
1.000000 0.000000
标准输入 复制文本
4
1000000000 999999999
999999999 -1000000000
-1000000000 -999999999
-999999999 1000000000
标准输出 复制文本
0.000000 0.000000

提示

17552352641488.png

登录以提交代码。
单点时限 5 秒
内存限制 128 MB
提交 40
通过 7