직각이등변삼각형 timer 2s memory 1024MB

2차원 평면 위에 서로 다른 N개의 점이 있다. 1 \le i \le 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이 구하고자 하는 길이가 된다.

[제약 조건]

• 주어지는 모든 수는 정수이다.

• 2 \le N \le 100\,000

• 1 \le i \le N인 각 i에 대해, -100\,000\,000 \le x_i,y_i \le 100\,000\,000

• 주어지는 N개의 점들은 모두 서로 다르다. 즉, 1 \le i \lt j \le N인 모든 i,j에 대해 x_i \neq x_j 또는 y_i \neq y_j이다.