Самые далёкие юрты


Отправить решение Решать в редакторе

Сложность: 85%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

На джайлоо Кёк-Жайык стоят 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.

Подсказка

Самые далёкие точки — вершины выпуклой оболочки, лежащие на параллельных опорных прямых («вращающиеся калиперы»).


Комментарии

Еще нет ни одного комментария.