Сегодня на страницах газеты «Геометрические головоломки» была опубликована необычная головоломка. На одной из ее страниц нарисованы две ломаные. Для решения головоломки необходимо найти две точки A и B , лежащие на разных ломаных, расстояние между которыми минимально.
Вася весь день ломал себе голову, однако придумать решение не смог. Вам нужно написать программу, которая поможет Васе.
В первой строке входного файла INPUT.TXT записано число N (2 ≤ N ≤ 1000) – количество узлов первой ломаной. В следующей строке перечислены N пар координат узлов первой ломаной. Все координаты целые и не превышают 104 по абсолютной величине. В третьей и четвертой строке описана вторая ломаная в аналогичном формате.
В первой строке выходного файла OUTPUT.TXT выведите расстояние между искомыми точками A и B. Во второй и третьей строке выведите соответственно координаты точки A и точки B. Выводите ответ с 9 знаками после запятой. Ваш ответ будет засчитан, если он отличается от правильного не более, чем на 10-4.
№ | INPUT.TXT | OUTPUT.TXT |
1 | 2
0 0 1 0
2
0 1 1 1 | 1.000000000
0.000000000 0.000000000
0.000000000 1.000000000 |
2 | 2
0 0 1 1
2
0 1 1 0 | 0.000000000
0.500000000 0.500000000
0.500000000 0.500000000 |