Самые далёкие юрты
На джайлоо Кёк-Жайык стоят n юрт, юрта i — в точке с целыми координатами (x[i], y[i]), никакие две юрты не стоят в одной точке. Чабаны хотят протянуть между двумя самыми далёкими друг от друга юртами сигнальную верёвку.
Найдите квадрат наибольшего расстояния между двумя юртами и количество пар юрт, расстояние между которыми равно этому наибольшему.
Входные данные
В первой строке — число n (2 ≤ n ≤ 2 · 10⁵). В каждой из следующих n строк — два целых числа x[i] y[i] (|x[i]|, |y[i]| ≤ 10⁹).
Выходные данные
Выведите два числа: квадрат наибольшего расстояния и количество неупорядоченных пар юрт на этом расстоянии.
Пример 1
Вход:
5
0 0
4 0
4 4
0 4
2 5
Выход:
32 2
Пояснение
Самые далёкие пары — противоположные углы квадрата 4 × 4: (0, 0) – (4, 4) и (0, 4) – (4, 0), квадрат расстояния 32. Юрта (2, 5) от каждого угла ближе.
Система оценивания
Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 25 % тестов n ≤ 300.
Подсказка
Самые далёкие точки — вершины выпуклой оболочки, лежащие на параллельных опорных прямых («вращающиеся калиперы»).
Комментарии