Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
Crane

Задача CRANE

На станції Глупов-Товарний використовуються підйомні крани спеціальної конструкції "Мостовий-Глуповський". Крюк такого крану підвішений до кількох блоків, що їздять по рейці, розміщеній горизонтально (на певній висоті). Завдяки цьому, крюк можна переміщати в будь-яку точку частини площини, обмежену многокутником спеціального вигляду: верхня сторона многокутника співпадає з рейкою крана, обидва внутрішні кути многокутника при цій стороні гострі, решта вершин многокутника розміщені довільним чином, але так, що многокутник виявляється опуклим. Крім того,станція має в розпорядженні пристрій, котрий дозволяє комбінувати дію двох кранів такого типу: простір досяжності крюка скомбінованого механізму точно такий, якби рейку другого крана підвісили (зі збереженням горизонтальності) на крюк першого.

Завдання. Напишіть програму, котра буде виконувати наступні дві дії:
1. За заданими областями досяжностей двох кранів знаходити область досяжності їхньої комбінації.
2. За заданими областю досяжності одного крану та потрібною областю досяжності, з'ясовувати, який потрібно взяти другий кран, щоб комбінація першого та другого кранів в точності співпадала з потрібною областю досяжності (або з'ясовувала, що це неможливо).

Технічні умови. Введіть з клавіатури спочатку 1 або 2 (на позначення того, яку задачу потрібно розв'язувати), потім йдуть дві області. Якщо розв'язується задача "1", то це області досяжності першого та другого кранів, якщо "2", то спочатку потрібну область досяжності а потім область досяжності першого крану. Усі області досяжності задаються у такому форматі: спочатку число N (3<=N<=1000) - кількість вершин у многокутнику, а далі N груп по 2 числа xi та yi - координати вершин цієї області в порядку зростання x - координати. Система координат завжди вибирається так, що перша вершина має координати (0; 0), вісь y напрямлена згори донизу. Всі вхідні координати - цілі числа, що не перевищують по модулю 106. Якщо розв'язується задача "2" і підібрати другий кран неможливо, то вивести на екран єдине число 0. Інакше вивести побудовану область досяжності (в тому ж форматі, що для вхідних даних).
Всі числа розділено пропусками. Якщо якісь координати є нецілими, достатньо виводити їх з точністю до найближчого цілого.

Приклади.

Введення>
2 5 0 0 10 40 20 50 30 40 40 0 3 0 0 10 10 20 0
Виведення> 3 0 0 10 40 20 0

Введення> 2 3 0 0 10 10 20 0 3 0 0 10 10 40 0
Виведення> 0

Введення> 1 3 0 0 10 10 20 0 3 0 0 10 10 40 0
Виведення> 4 0 0 20 20 50 10 60 0


© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"