Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

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.TXTOUTPUT.TXT
14
-10 0
10 0
3 1
1 -1
2.000000

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483