ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Ural SU contest. Petrozavodsk training camp. Winter 2008

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

C. Пусти козла в огород 6

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
Уже седьмой год идёт война между соседями Василием Петровичем и Петром Васильевичем. Никто уже и не помнит, из-за чего она началась. Никто не может точно сказать, кто из соседей первым увидел в своём огороде с капустой соседского козла. Но с тех пор, как только один сосед отлучится на минутку, второй непременно идёт выгуливать своих козлов к нему в огород. И Василий Петрович, и Пётр Васильевич давно к этому привыкли, и очередная обглоданная грядка с капустой уже не вызывает удивления ни у кого из соседей.
Старой враждой Василия Петровича и Петра Васильевича решил воспользоваться Иван Иванович. Когда-то Пётр Васильевич не дал ему денег в долг, и пришла пора отомстить ему за этот мерзкий поступок. Иван Иванович дождался, пока Пётр Васильевич уедет в город по делам, после чего привёл свою козу в его огород (надеясь, что, обнаружив съеденную капусту, Пётр Васильевич обвинит в этом козлов Василия Петровича).
Придя в огород Петра Васильевича, Иван Иванович обнаружил, что там осталась последняя грядка с капустой, да и то на ней мирно пасся козлёнок Василия Петровича. Иван Иванович решил воткнуть вне грядки колышек и привязать к нему свою козу и козлёнка Василия Петровича так, чтобы коза могла достать до любой точки грядки, а козлёнок не мог достать ни до одной внутренней точки грядки. Известно, что длина верёвки, которой Иван Иванович хочет привязать козу, равна R, а длина верёвки, которой он хочет привязать козлёнка, равна r. Помогите Ивану Ивановичу выбрать нужное место для колышка.

Исходные данные

Грядка имеет форму выпуклого N-угольника. В первой строке дано целое число N (3 ≤ N ≤ 50). Далее в N строках перечислены координаты вершин N-угольника (XiYi) — целые числа, по модулю не превышающие 1000. Вершины перечислены в порядке обхода. В последней строке записаны целые числа r и R. 1 ≤ r < R ≤ 1000. Размерами колышка, козы и козлёнка можно пренебречь.

Результат

Если существует способ привязать козу с козлёнком, выведите через пробел пару чисел — координаты точки, куда можно вбить колышек. Числа должны быть округлены до 10−6. Если такого способа не существует, выведите «No solution».

Примеры

исходные данныерезультат
4
0 0
0 1
1 1
1 0
1 3
0.500000 -1.000000
3
0 0
0 14
2 7
8 10
No solution
Автор задачи: Алексей Самсонов
Источник задачи: Ural SU Contest. Petrozavodsk Winter Session, January 2008
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1662. Пусти козла в огород 6