적절한 좌표 지도

어떤 나라가 초고속 통신망을 새로 깐다. 회선은 모두 단방향이고, 두 끝점을 잇는 직선으로 놓인다. 회선의 끝점 장비가 비싸서 노드는 링 하나로 묶는다. 링은 모든 노드에 들어오는 회선이 하나, 나가는 회선이 하나씩 있는 연결 그래프다. 링으로 묶으면 모든 노드가 다른 노드에 직접 또는 중간 노드를 거쳐 데이터를 보낼 수 있다.

후보 지점 $N$개의 목록은 이미 정해져 있고, 정부는 후보 지점 $N$개를 모두 노드로 쓰려 한다. 통신부 장관은 조건을 하나 더 걸었다.

노드 둘을 링의 양 끝으로 지명해 각각 $A$와 $B$라 부른다. 그리고 적절한 좌표 지도(ACM)를 세운다. 원점은 $A$이고, 양의 $x$축은 $A$에서 $B$를 향하며, 길이 단위는 평소 쓰는 것과 같다. 링을 따라 $A$에서 $B$로 가는 경로는 ACM $x$값이 감소하지 않아야 하고, $B$에서 $A$로 가는 경로는 ACM $x$값이 증가하지 않아야 한다. 장관은 앞의 경로를 나가는 구간, 뒤의 경로를 돌아오는 구간이라 부른다.

이 조건을 만족하는 링은 여럿일 수 있고, 어느 노드 둘을 $A$와 $B$로 쓸지도 직접 고른다. 이런 선택을 전부 놓고 볼 때, 링에서 이웃한 두 노드의 ACM $x$값 차이의 절댓값 중 최솟값이 가장 커지는 링을 고른다. 그 최솟값을 구하라.

한쪽 구간의 회선은 다른 쪽 구간의 회선이나 노드와 교차해도 서로 간섭하지 않는다. 실제로는 높이를 달리 두어 간섭을 피하지만, 이 문제는 교차 제한이 없는 2차원 문제로 풀면 된다.

그림 1: (a) 점의 집합. (b) $A$와 $B$를 고르면 ACM $x$축도 정해진다. (c) 각 점은 ACM $x$축 기준의 $x$값을 얻는다. (d) 조건을 만족하는 링의 예.

입력은 테스트 케이스 하나로 이루어진다.

첫 줄에 후보 지점의 개수 $N$이 주어진다 ($3 \le N \le 100\,000$). 다음 $N$개의 줄에는 각 후보 지점의 $x$좌표와 $y$좌표가 정수로 주어진다 ($-10^9 \le x, y \le 10^9$). $N$개의 점은 서로 다르다. 이 점들의 볼록 껍질은 꼭짓점이 3개 이상 30개 이하다.

장관이 요구한 값을 소수점 아래 여섯 자리로 출력한다.