Задача 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