Codeforces Round 514 (Div. 2) |
---|
Закончено |
В лесу, который мы представляем как плоскость, живут $$$n$$$ редких животных. Животное номер $$$i$$$ имеет логово в точке $$$(x_{i}, y_{i})$$$. В целях защиты этих животных было решено создать заповедник, имеющий форму круга, в котором должны находиться все логова редких животных.
Также через лес протекает единственная река, из которой пьют все животные, в связи с чем она должна иметь хотя бы одну общую точку с заповедником. С другой стороны, по реке постоянно ходят корабли, чему может помешать наличие более чем одной общей точки реки и заповедника. Таким образом, необходимо, чтобы заповедник и река имели ровно одну общую точку.
Для вашего удобства ученые уже сделали преобразование координат такое, что теперь река задана уравнением $$$y = 0$$$. Определите, возможно ли построить заповедник и найдите минимальный радиус заповедника, удовлетворяющего заданным условиям.
В первой строке дано целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — количество животных.
В каждой из следующих $$$n$$$ строк находятся два целых числа $$$x_{i}$$$, $$$y_{i}$$$ ($$$-10^7 \le x_{i}, y_{i} \le 10^7$$$) — координаты логова $$$i$$$-го животного. Гарантируется, что $$$y_{i} \neq 0$$$, а также, что никакие два расположения логова не совпадают.
Если заповедник невозможно построить, выведите $$$-1$$$. Иначе выведите одно вещественное число — минимальный радиус заповедника. Ваш ответ будет засчитан, если абсолютная или относительная погрешность вашего ответа не превышает $$$10^{-6}$$$.
Формально, пусть ваш ответ равен $$$a$$$, а ответ жюри равен $$$b$$$. Ваш ответ будет зачтен, если $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$.
1
0 1
0.5
3
0 1
0 2
0 -3
-1
2
0 1
1 1
0.625
В первом примере оптимально построить заповедник радиуса $$$0.5$$$ с центром в точке $$$(0,\ 0.5)$$$.
Во втором примере невозможно построить заповедник.
В третьем примере оптимально построить заповедник радиуса $$$\frac{5}{8}$$$ с центром в точке $$$(\frac{1}{2},\ \frac{5}{8})$$$.
Название |
---|