← 返回题目列表

Codeforces · 274/C

C. 最后一洞!

中文机器翻译题面 查看原题

鹿邑在平面上有n个圆圈。第 i 个圆的圆心为 (xi, yi)。此时零个圆圈开始同时增长。换句话说,每个圆在时间 t(t > 0)时的半径等于 t。这些圆圈在无限的白色平面上绘制为黑色圆盘。所以在每一时刻,平面都由几个黑色和白色区域组成。请注意,圆圈在增长时可能会重叠。

我们将孔定义为封闭的、相连的白色区域。例如,该图包含两个用红色边框显示的孔。在生长过程中可能会产生一些孔,并且很容易看到每个产生的孔最终都会消失。鲁伊要求你找到一个时间点,让最后一个洞消失。换句话说,你应该找到第一个时刻,这样之后就看不到任何洞了。

输入

输入的第一行包含整数 n (1 ≤ n ≤ 100)。接下来的 n 行每行包含两个整数 xi 和 yi (- 104 ≤ xi, yi ≤ 104),表示第 i 个圆的位置。

保证没有两个圆的圆心位于同一点。

输出

打印最后一个孔消失的时刻。如果不存在我们可以找到漏洞的时刻,则打印 -1。

如果绝对或相对误差不超过 10 - 4,则答案将被视为正确。

示例

输入 #1

3
0 0
1 1
2 2

输出 #1

-1

输入 #2

4
0 0
0 2
2 2
2 0

输出 #2

1.414214

输入 #3

4
0 1
0 -1
-2 0
4 0

输出 #3

2.125000