Уже седьмой год идёт война между соседями Василием Петровичем и Петром Васильевичем.
Никто уже и не помнит, из-за чего она началась. Никто не может точно сказать, кто
из соседей первым увидел в своём огороде с капустой соседского козла. Но с тех пор,
как только один сосед отлучится на минутку, второй непременно идёт выгуливать своих
козлов к нему в огород. И Василий Петрович, и Пётр Васильевич давно к этому привыкли,
и очередная обглоданная грядка с капустой уже не вызывает удивления ни у кого из соседей.
Старой враждой Василия Петровича и Петра Васильевича решил воспользоваться Иван Иванович.
Когда-то Пётр Васильевич не дал ему денег в долг, и пришла пора отомстить ему за этот
мерзкий поступок. Иван Иванович дождался, пока Пётр Васильевич уедет в город по делам,
после чего привёл свою козу в его огород (надеясь, что, обнаружив съеденную капусту, Пётр
Васильевич обвинит в этом козлов Василия Петровича).
Придя в огород Петра Васильевича, Иван Иванович обнаружил, что там осталась последняя
грядка с капустой, да и то на ней мирно пасся козлёнок Василия Петровича. Иван Иванович
решил воткнуть вне грядки колышек и привязать к нему свою козу и козлёнка Василия Петровича так,
чтобы коза могла достать до любой точки грядки, а козлёнок не мог достать ни до одной внутренней точки грядки.
Известно, что длина верёвки, которой Иван Иванович хочет привязать козу, равна R, а длина
верёвки, которой он хочет привязать козлёнка, равна r. Помогите Ивану Ивановичу выбрать
нужное место для колышка.
Исходные данные
Грядка имеет форму выпуклого N-угольника. В первой строке дано целое число N (3 ≤ N ≤ 50).
Далее в N строках перечислены координаты вершин N-угольника (Xi, Yi) —
целые числа, по модулю не превышающие 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