Авиалинии

В стране n городов, расположенных в точках с заданными координатами. Известно, что никакие два города не лежат на одной прямой. Некоторые пары городов соединены авиалиниями. Президент новой авиакомпании провел анализ имеющейся сети авиалиний и решил соединить авиалинией два города, которые до этого еще не были соединены прямой линией, и полет между которыми на самолетах с пересадками, занимает наибольшее время (пропорциональное суммарной длине перелетов) или, вообще, невозможен. В этом случае время считается равным бесконечности. Если у нескольких пар городов эта величина одинакова, то выбирается пара городов, один из которых имеет наименьший номер, а если и это не определяет нужную пару, то наименьший номер должен иметь второй город. Так он поступает k раз. Требуется определить, какие два города после всех нововведений окажутся самыми удаленными друг от друга.

Ограничения.

n, k < 100; m (количество изначально имеющихся авиалиний) < 1000; все координаты городов - целые неотрицательные числа, не превышающие 32000; время тестирования каждого теста - 3 сек.

Исходные данные

расположены в файле input.txt и имеют следующий формат: в первой строке через пробел следуют три числа n k m; в последующих n строках расположены координаты городов; в последующих m строках указаны имеющиеся в стране авиалинии, каждая линия задается двумя целыми числами - номерами городов, которые она соединяет.

Результат

- номера искомых городов - должен быть выведен на экран. Если у нескольких пар городов окажется наибольшее удаление, вывести их все.

Пример файла input.txt
3 2 1
1 1
1 4
5 1
12
Результат, соответствующий примеру: 5

Луч света в углу

Имеется угол, равный a. Один из лучей угла направлен по оси Ox от начала координат, другой расположен в первой координатной четверти. Внутри угла из заданной точки в заданном направлении пускается луч света, который, встречаясь со сторонами угла, отражается по закону "угол падения равен углу отражения". Требуется определить, сколько раз луч отразиться от сторон и в какой точке произойдет последнее отражение.

Ограничения.

0 < a < 90o Величина угла - целое число в градусах. Координаты исходной точки - целые положительные числа, не превышающие 32000. Напрвление света задается указанием точки с целыми координатами, в чью сторону первый раз пущен луч. Исходная точка гарантированно находится внутри угла.

Исходные данные

расположены в файле input.txt и имеют следующий формат: в первой строке число a - целое число в градусах; во второй строке - координаты исходной точки; в третьей строке - координаты точки, в чью сторону первый раз пущен луч - два целых числа.

Результат

должен быть выведен на экран. Координаты точки последнего отражения следует вывести с точностью до 0.0001

Пример файла input.txt:
45
4 2
5 -3
Результат, соответствующий примеру:
2 (количество отражений)
5.5 5.5 (координаты точки последнего отражения)

Rambler's Top100