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

1199. Мышка

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
На кухне живёт мышка. Также на кухне живёт кошка и лежит сыр. Координаты сыра и мышки известны, а кошка спит. Наконец, на кухне стоит мебель. Мебель — это набор выпуклых многоугольников. Мышка хочет добраться до сыра как можно более незаметно. Точка пути называется опасной, если расстояние до ближайшего предмета мебели больше 10 см. Необходимо найти для мышки наименее опасный маршрут, то есть такой, в котором сумма длин опасных участков будет минимальной.

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

В первой строке через пробел четыре числа xm, ym, xc, yc — координаты мышки (xmym) и сыра (xcyc). Во второй строке целое число N (0 ≤ N ≤ 100) — количество предметов мебели. В следующих строках даны N описаний предметов. Каждое описание начинается с целого числа K (3 ≤ K ≤ 10) в отдельной строке — количества вершин многоугольника. В следующих K строках, по два числа в строке, описаны координаты вершин. Известно, что расстояние между любыми двумя точками различных многоугольников больше 20 см. (Чтобы кошке было удобнее ловить мышку.) Вы также можете считать, что ни мышка, ни сыр не лежат внутри одного из многоугольников. Все координаты даны в метрах и имеют не более трёх знаков после десятичной точки. Координаты не превосходят 105 по модулю.

Результат

Путь мышки необходимо представить в виде ломаной линии. В первой строке выведите количество вершин ломаной (включая начальную и конечную). Далее должны следовать координаты вершин, по одной паре на строку. Координаты должны быть выведены с точностью до 10-4. Каждый отрезок пути должен быть целиком опасным или безопасным (возможно, за исключением конечных точек). Ломаная не может содержать более 1000 вершин.

Пример

исходные данныерезультат
1.0 1.5 0.0 1.5
1
4
0.0 0.0
0.0 1.0
1.0 1.0
1.0 0.0
4
1.0 1.5
1.0 1.1
0.0 1.1
0.0 1.5
Автор задачи: Никита Рыбак