На плоскости заданы N точек с целочисленными координатами. Требуется найти среди них пару самых ближних и пару самых дальних друг от друга точек.
Первая строка входного файла INPUT.TXT содержит целое число N (2 ≤ N ≤ 1000) – количество точек. Далее следует N строк пар целых чисел (Xi,Yi), описывающих координаты первой, второй и т.д. точек соответственно (-109 ≤ Xi,Yi ≤ 109).
В первой строке выходного файла OUTPUT.TXT выведите через пробел номера пары ближних друг к другу точек. Во второй строке выведите номера пары дальних друг от друга точек. В случае неоднозначности определения ответа выведите любой.
№ | INPUT.TXT | OUTPUT.TXT |
1 | 5
0 0
1 2
-3 4
9 6
5 -2 | 1 2 3 4 |
2 | 10
3 8
-2 5
9 3
0 0
6 8
-5 4
9 0
2 -6
-1 -1
-9 7 | 4 9 7 10 |