そっか、一個思い出した。君は助けない(▼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 |
提示