| Codeforces Round 168 (Div. 1) |
|---|
| Закончено |
У Луи есть n кругов на плоскости. Центр круга номер i находится в точке (xi, yi). В момент времени ноль круги начинают одновременно расти. Иными словами, радиус каждого круга в момент времени t (t > 0) равняется t. Круги изображаются в виде черных дисков на бесконечной белой плоскости. Итак, в каждый момент плоскость состоит из нескольких черных и белых регионов. Заметьте, что круги, разрастаясь, могут накладываться друг на друга.
Будем называть дырой замкнутую, связную белую область. Например, на рисунке изображены две дыры, обозначенные красной границей. Пока круги растут, они могут создать новые дыры и легко видеть, что каждая созданная дыра в конце концов исчезнет. Луи просит Вас найти момент времени, когда исчезает последняя дыра. Другими словами, первый момент времени, после которого никогда не будет ни одной дыры на плоскости.
Первая строка входных данных содержит целое число n (1 ≤ n ≤ 100). Каждая из следующих n строк содержит по два целых числа xi и yi ( - 104 ≤ xi, yi ≤ 104), обозначающих расположение i-того круга.
Гарантируется, что никакие два круга не имеют центра в одной и той же точке.
Выведите момент времени, когда исчезает последняя дыра. Если ни в один момент времени не существует ни одной дыры, выведите -1.
Ответ будет считаться правильным, если абсолютная или относительная погрешность не превышают 10 - 4.
3
0 0
1 1
2 2
-1
4
0 0
0 2
2 2
2 0
1.414214
4
0 1
0 -1
-2 0
4 0
2.125000
