Интересная загадка

시간 제한2초메모리 제한1024 MB

요약

점들을 두 개의 비어 있지 않은 집합으로 나눠 서로 다른 집합에 속한 두 점 사이 거리의 최솟값을 최대화하고, 그 제곱을 구한다.

난이도: 보통10점 중 7점
유형: 기하, 정렬, 완전 탐색, 구현
정답자: 아직 제출이 없습니다

문제

Однажды Эркюль Пуаро заскучал, и Мсье Бук решил его развлечь.

Мсье Бук взял клетчатый листок бумаги и отметил на нём несколько точек с целочисленными координатами. После этого он попросил Эркюля узнать максимальное $d$ такое, что отмеченные точки можно разбить на два непустых множества так, чтобы для каждой пары точек из разных множеств расстояние было больше или равно $d$ .

Так как мсье Бук большой любитель целых чисел, в качестве ответа он попросил Эркюля выдать $d^2$ . Можно доказать, что $d^2$ --- всегда целое число при данных ограничениях.

Эркюль быстро справился с данной задачей, а справитесь ли Вы?

입력

Первая строка содержит одно число $n$ --- количество точек, которые отметил мсье Бук ( $2 \le n \le 2000$ ). Каждая из последующих $n$ строк содержит по два целых числа $x$ , $y$ --- координаты точек ( $-10^9 \le x, y \le 10^9$ ). Все отмеченные точки различны.

출력

Выведите одно число равное $d^2$ .

예제2

예제 1
입력
```
4
0 1
1 0
0 0
1 1
```
예상 출력
```
1
```
예제 2
입력
```
7
0 1
1 0
0 0
1 1
1 3
2 2
2 3
```
예상 출력
```
2
```