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