문제
KOI 사막에 작은 마을이 있다. 현재 KOI 사막은 개발 사업이 진행중이므로 편의를 위해 길고 좁은 운하를 건설하려고 한다. 운하는 북쪽에서 남쪽으로 하나, 동쪽에서 서쪽으로 하나 해서 총 두 개를 건설하려고 한다. 운하는 다양한 목적으로 사용되므로 마을 사람들이 접근하기 쉽도록 건설하려고 한다.
운하 위치에 대하여 다양한 논의가 나온 결과, 운하는 마을에 있는 모든 집과 운하 사이의 최대 거리가 최소화되도록 지어야 한다는 결론이 나왔다.
n개 집의 좌표가 주어지면, 적절하게 운하를 건설하여 집과 운하 사이의 최대 거리를 최소화한 다음 그 거리를 출력하는 프로그램을 작성하여라.
n개 집은 x-축과 y-축이 있는 좌표평면 위에 있으며, x-축은 서쪽과 동쪽을 이으며 y-축은 남쪽과 북쪽을 잇는다. 두 운하는 좌표평면 위에 있는 폭이 0인 두 직선으로 생각할 수 있으며 하나는 x-축과, 다른 하나는 y-축과 평행하다. 두 운하가 만나는 지점은 어디든지 될 수 있으며 운하가 집을 지날 수 있다. 집과 운하 사이의 거리는 두 운하 중에서 더 가까운 운하와의 거리이다. 즉, 운하 위에 있는 집은 운하와의 거리가 0이다.
입력
입력은 표준입력을 사용한다. 첫째 줄에는 사막에 있는 집의 수 n (1 ≤ n ≤ 300,000)이 주어진다. 둘째 줄부터 n 개의 줄에는 각 집의 x, y 좌표가 주어진다. 모든 좌표는 -109 이상 109 이하의 정수이다. 여러 집이 같은 좌표를 가질 수 있음에 유의하여라.
출력
출력은 표준출력을 사용한다. 첫째 줄에 적절하게 운하를 건설했을 때 집과 운하 사이의 최대 거리를 출력한다. 정답은 소수점 둘째 자리에서 반올림하여 소수점 아래 한 자리까지 출력한다.
예제 #1
5
0 0
0 23
34 0
1 -21
-74 1
0.5
예제 #2
10
0 2
3 0
-10 0
0 23
0 -162
0 11
-235 0
-213 0
32 0
0 732
0.0
출처
2019 ICPC Seoul 예선 D
로그인해야 코드를 작성할 수 있어요.