|
Clear World and Brothers
(Время: 3 сек. Память: 16 Мб Сложность: 46%)
Наконец в деревнях Виллорибо и Виллобаджо закончились праздники. Перемыта вся посуда! Этот процесс прошел так быстро и непринужденно, что братьями Карлионе было решено открыть сеть агентств «Clear World and Brothers», специализирующихся на профессиональном мытье посуды. В области Новая Берляндия, где и находятся знаменитые деревни, всего N деревень. Система координат введена так, что Виллорибо имеет координаты (x1, 0), а Виллобаджо - (x2, 0). Координаты всех деревень целые числа не превосходящие по модулю 106. Вы работаете на мистера Берлионе старшего и ваша задача найти оптимальное расположение для регионального отделения «Clear World and Brothers», то есть сумма расстояний от агентства до всех деревень должна быть наименьшей и агентство обязательно должно располагаться на прямолинейном шоссе Виллорибо-Виллобаджо (возможно расположение не только внутри, но и на границе отрезка).
Входные данные
В первой строке входного файла INPUT.TXT записано натуральное число N (2 ≤ N ≤ 15000). Далее в N строках записаны пары координат всех вершин. Виллорибо и Виллобаджо первая и вторая деревня соответственно. Возможно, что сколько-то деревень расположены так близко, что их координаты совпадают.
Выходные данные
В выходной файл OUTPUT.TXT выведите абсциссу оптимального расположения агентства. Разрешается абсолютная погрешность не более единицы.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 4
-10 0
10 0
3 1
1 -1 | 2.000000 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
