60001 직각이등변삼각형 Gold V

문제

$2$차원 평면 위에 서로 다른 $N$개의 점이 있다. $1 ≤ i ≤ N$인 각 $i$에 대해, $i$번째 점의 좌표는 $(x_i , y_i )$이다.

이등변삼각형이란, 세 변 중 길이가 같은 두 변이 있는 삼각형을 의미한다. 직각삼각형이란, 한 내각이 직각($90^\circ$) 인 삼각형을 의미한다. 직각삼각형의 빗변이란, 직각삼각형에서 직각과 마주보는 변을 의미하며, 길이가 가장 긴 변이기도 하다.

직각이등변삼각형이란, 직각삼각형이면서 이등변삼각형인 삼각형을 의미한다. 즉, 삼각형의 한 내각이 직각이고, 빗변이 아닌 두 변의 길이가 서로 같은 삼각형을 의미한다.

다음 두 조건을 모두 만족하는 직각이등변삼각형 중 빗변의 길이가 가장 짧은 것의 빗변의 길이를 구하는 프로그램을 작성하라.

• $N$개의 점 $(x_1 , y_1 ),(x_2 , y_2 ), \cdots ,(x_N , y_N )$은 모두 직각이등변삼각형의 경계(변 위)나 내부에 위치한다. 어떤 점이 직각이등변삼각형의 꼭짓점에 위치하는 경우도 경계에 위치한 것으로 간주한다.
• 빗변이 $x$축과 평행하다. 즉, 직각이등변삼각형의 빗변의 두 끝점의 $y$좌표가 같다. 이는 다음 그림과 같이 직각이 빗변의 위쪽에 있는 직각이등변삼각형과 직각이 빗변의 아래쪽에 있는 두 종류의 직각이등변삼각형만 조건을 만족함을 의미한다.

예를 들어, 다음 그림과 같이 $5$개의 점 $(0, −1), (2, 4), (4, −1), (−1, 2), (3, 1)$이 주어졌다고 하자. 점은 크기를 갖지 않으나, 그림에서는 편의를 위해 점을 원으로 표현하였다.

직각이 빗변의 위쪽에 있는 직각이등변삼각형 중 빗변의 길이가 가장 짧은 것은 아래 그림과 같이 세 꼭짓점이 $(1.5, 4.5),(−4, −1),(7, −1)$인 삼각형이며, 이 직각이등변삼각형의 빗변의 길이는 $11$이다.

직각이 빗변의 아래쪽에 있는 직각이등변삼각형 중 빗변의 길이가 가장 짧은 것은 아래 그림과 같이 세 꼭짓점이 $(2, −3),(−5, 4),(9, 4)$인 삼각형이며, 이 직각이등변삼각형의 빗변의 길이는 $14$이다.

두 직각이등변삼각형 중 빗변의 길이가 짧은 것은 직각이 빗변의 위쪽에 있는 경우이므로 $11$이 구하고자 하는 길이가 된다.

입력

첫 번째 줄에 정수 $N$이 주어진다.

다음 $N$개의 줄 중 $i$ ($1 ≤ i ≤ N$)번째 줄에는 두 정수 $x_i$ 와 $y_i$가 공백을 사이에 두고 주어진다.

출력

첫 번째 줄에 조건을 모두 만족하는 직각이등변삼각형 중 빗변의 길이가 가장 짧은 것의 빗변의 길이를 출력한다. 답이 항상 정수임을 증명할 수 있다.

제한

• 주어지는 모든 수는 정수이다.
• $2 ≤ N ≤ 100\, 000$
• $1 ≤ i ≤ N$인 각 $i$에 대해, $−100\, 000\, 000 ≤ x_i , y_i ≤ 100\, 000\, 000$
• 주어지는 $N$개의 점들은 모두 서로 다르다.
• 즉, $1 ≤ i < j ≤ N$인 모든 $i$, $j$에 대해 $x_i \ne x_j$ 또는 $y_i \ne y_j$이다.

서브태스크

번호	배점	제한
1	10	$N ≤ 2$
2	18	$N ≤ 3$
3	20	$N ≤ 50$이고, $1 ≤ i ≤ N$인 각 $i$에 대해 $−30 ≤ x_i , y_i ≤ 30$이다.
4	10	$N ≤ 50$
5	4	$2 ≤ i ≤ N$인 각 $i$에 대해 $y_i = y_{i-1}$이다. 즉, 모든 점의 $y$좌표가 서로 같다.
6	6	$1 ≤ i ≤ N$인 각 $i$에 대해 $x_i = y_i$이다.
7	10	주어진 조건을 모두 만족하면서 빗변의 길이가 가장 짧은 직각이등변삼각형 중 적어도 하나는 빗변의 중점이 $(0, 0)$이다.
8	22	추가 제약 조건 없음.

힌트

예제 1 설명

세 꼭짓점이 $(−1, 0),(2, 3),(5, 0)$인 직각이등변삼각형이 모든 조건을 만족하며, 빗변의 길이가 $6$으로 가장 짧다.

예제 2 설명

모든 조건을 만족하며 빗변의 길이가 $7$인 직각이등변삼각형은 다음과 같이 두 가지 있다.

• 세 꼭짓점이 $(0, 0),(7, 0),(3.5, 3.5)$인 삼각형

• 세 꼭짓점이 $(−2, 2),(5, 2),(1.5, −1.5)$인 삼각형

3
0 0
2 3
4 0

6

2
0 0
5 2

7

4
1 5
3 2
6 6
7 4

10