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

Открытый чемпионат УрФУ 2011

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

D. Остров Меркет

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Меркет — необитаемый остров в Балтийском море. Исторически западная часть острова принадлежит Швеции, а восточная часть — Финляндии. В 1885 году финны построили на острове маяк. Точных карт острова тогда ещё не существовало, и впоследствии шведская сторона заявила, что маяк находится на её территории. Чтобы урегулировать территориальный спор, было решено провести по острову границу между Швецией и Финляндией так, чтобы площади шведской и финской частей острова совпадали, а маяк целиком находился на территории Финляндии.
Будем считать остров Меркет прямоугольником на плоскости, а маяк — квадратом, расположенным строго внутри этого прямоугольника. Стороны прямоугольника и квадрата параллельны осям координат, юго-западный угол острова имеет координаты (0, 0), а северо-восточный — (w, h). Граница должна являться ломаной с вершинами в точках с целыми координатами, проходящей от северного побережья острова к южному. Отрезки ломаной должны быть параллельны осям координат. Граница не должна иметь общих точек с западным и восточным побережьями острова и должна иметь ровно по одной общей точке с северным и южным побережьями. Граница не может проходить через маяк, но может касаться его.
Определите, каким образом нужно провести по острову границу между странами.

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

В первой строке записаны целые числа w и h — размеры острова Меркет (3 ≤ w, h ≤ 106; w · h чётно). Во второй строке записаны целые числа x, y и d — координаты юго-западного угла маяка и длина стороны маяка (d > 0; 0 < x < wd; 0 < y < hd).

Результат

В первой строке выведите количество вершин ломаной, а в следующих строках — целые координаты этих вершин, следуя от вершины на северном побережье к вершине на южном. Вертикальные и горизонтальные звенья ломаной должны чередоваться, первое и последнее звено должны быть вертикальными. Все звенья должны иметь ненулевую длину. Ломаная не должна иметь самопересечений и самокасаний. Количество вершин в ломаной не должно превосходить 1 000. Если границу можно провести несколькими способами, выведите любой из них. Если провести границу с соблюдением всех описанных условий нельзя, выведите «Impossible».

Примеры

исходные данныерезультат
6 3
1 1 1
6
4 3
4 2
1 2
1 1
4 1
4 0
10 10
1 1 8
Impossible
Автор задачи: Евгений Курпилянский (идея — Леонид Волков)
Источник задачи: Открытый командный чемпионат УрФУ по программированию — 2011
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1865. Остров Меркет