운하

평평하고 건조한 사막에 자리한 작은 마을 Aissippissi에 사람들이 정착하기 시작한 것은 그리 오래되지 않았다. Aissippissi는 아직 개발 중이며, 정부는 마을을 가로지르는 운하를 건설할 계획을 세웠다. 운하는 각각 남북 방향과 동서 방향으로 뻗은 두 개의 길고 좁은 수로로 이루어지며, 두 수로는 한 점에서 교차한다. Aissippissi 주민들에게 운하는 여러모로 유용하므로, 운하에 쉽게 접근할 수 있는지는 설계에서 매우 중요한 기준이다.

문제는 운하를 어디에 둘 것인가이다. 운하의 위치에 따라 주민들이 운하까지 이동하는 거리가 크게 달라지기 때문이다. 이 문제를 해결하기 위해 당신은 아이디어를 떠올렸다. 두 수로로 이루어진 운하를, 모든 집에서 운하까지의 거리 중 최댓값이 최소가 되도록 배치하려는 것이다.

Aissippissi에 있는 n채의 집 좌표가 주어질 때, n채의 집에서 운하까지의 거리 중 최댓값을 최소로 만드는 최적의 운하 위치를 구하고 그때의 거리를 출력하는 프로그램을 작성하라.

n채의 집은 x축과 y축이 있는 평면 위의 점이라고 가정한다. x축은 서쪽에서 동쪽 방향을, y축은 남쪽에서 북쪽 방향을 따른다. 따라서 운하의 두 수로는 평면 위에서 각각 x축과 y축에 평행한 두 직선으로 본다. 교차점은 평면 위의 임의의 점이 될 수 있다. 또한 수로는 지면 약간 아래에 건설되므로 일부 집을 지나갈 수도 있다. 집에서 운하까지의 거리는 평면에서 더 가까운 수로까지의 직선 거리이다. 따라서 수로 위에 정확히 놓인 집에서 운하까지의 거리는 0이다.

프로그램은 표준 입력에서 데이터를 읽는다. 입력의 첫 줄에는 정수 n (1 ≤ n ≤ 300,000)이 주어지며, n은 Aissippissi에 있는 집의 수이다. 이어지는 n개의 줄에는 각각 두 정수가 주어지며, 각 정수는 −10^9 이상 10^9 이하로 각 집의 x좌표와 y좌표를 나타낸다. 좌표가 같은 집이 둘 이상 있을 수 있다.

프로그램은 표준 출력에 결과를 쓴다. 최댓값 거리를 최소로 만드는 최적의 운하에 대해 집에서 운하까지의 거리 중 최댓값을 소수 첫째 자리에서 반올림하여 실수 하나로 한 줄에 출력하라.