Емблема центру  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


 


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