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


Годинник
 
Subway

Задача Subway

"Підземний хід". Задачею, що наведено нижче, серйозно займались в епоху феодалізму. Вимагався ефективний те економний розв'язок. Так і зародилась наукова організація праці.
Фортеці  середньовіччя часто мали вигляд опуклих багатокутників. Дано плани двох фортець. Визначіть, де потрібно прорити підземний хід з однієї фортеці в іншу так, щоб його довжина була б найменшою.

Технічні умови:
Ваша програма повинна зчитати вхідні дані з клавіатури. В першому рядку знаходиться ціле число M - число кутів у першій фортеці (1<M<20). В наступних M рядках перераховані (не обов'язково в порядку обхода) координати кутів фортеці Xi, Yi  (-1000.000<Xi,Yi<1000.000). Потім слідує кількість і координати кутів другої фортеці.
Ваша програма повинна розв'язати задачу і надрукувати на екрані координати початку підземного ходу, а в другій - кінця. Результат потрібно знайти з точністю до 0.001.
 

Приклади:
Введення:

5
2.000 1.000
4.000 2.000
2.000 4.000
4.000 4.000
3.000 6.000
3
6.000 1.000
5.000 3.000
7.000 5.000
Виведення:
4.000 3.000
5.000 3.000


 


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