KOI 사막에 작은 마을이 있다. 현재 KOI 사막은 개발 사업이 진행중이므로 편의를 위해 길고 좁은 운하를 건설하려고 한다. 운하는 북쪽에서 남쪽으로 하나, 동쪽에서 서쪽으로 하나 해서 총 두 개를 건설하려고 한다. 운하는 다양한 목적으로 사용되므로 마을 사람들이 접근하기 쉽도록 건설하려고 한다.

운하 위치에 대하여 다양한 논의가 나온 결과, 운하는 마을에 있는 모든 집과 운하 사이의 최대 거리가 최소화되도록 지어야 한다는 결론이 나왔다.

n개 집의 좌표가 주어지면, 적절하게 운하를 건설하여 집과 운하 사이의 최대 거리를 최소화한 다음 그 거리를 출력하는 프로그램을 작성하여라.

n개 집은 x-축과 y-축이 있는 좌표평면 위에 있으며, x-축은 서쪽과 동쪽을 이으며 y-축은 남쪽과 북쪽을 잇는다. 두 운하는 좌표평면 위에 있는 폭이 0인 두 직선으로 생각할 수 있으며 하나는 x-축과, 다른 하나는 y-축과 평행하다. 두 운하가 만나는 지점은 어디든지 될 수 있으며 운하가 집을 지날 수 있다. 집과 운하 사이의 거리는 두 운하 중에서 더 가까운 운하와의 거리이다. 즉, 운하 위에 있는 집은 운하와의 거리가 0이다.

#4571 upload 3 done 1 how_to_reg 1

운하 timer 4s memory 512MB

#4571

운하 4s 512MB