17625번 - 고압선 스페셜 저지

새로 건설하게 될 신도시에 대한 기반시설 설계가 진행중이다. 원활하고 안정적인 전력 공급을 위해 고압선을 이 도시를 가로지르도록 하기로 하였다. 하지만 고압선은 강력한 전자기장을 유도하기 때문에 거주지에서는 가능한 거리를 두고 싶다.

도시의 거주지역을 평면 상의 N개의 점으로 표현하고, 고압선은 이 평면 상에서 완전한 직선 형태를 가진다고 가정하자. 이때, 고압선까지의 거리가 가장 가까운 거주지가 가장 큰 영향을 받게 되기 때문에, 최적의 고압선은 도시를 가로지르면서도 각 거주지점까지의 직선거리의 최솟값을 최대화해야 한다. 고압선(직선)이 도시를 가로지른다는 것은 구체적으로 고압선을 기준으로 양쪽에 모두 거주지점이 하나 이상 존재한다는 것을 의미한다.

최적의 고압선 형태를 계산하고 이때의 각 거주지점까지의 직선거리의 최솟값을 출력하는 프로그램을 작성하시오.

첫 번째 줄에 신도시의 거주지점의 개수 N (2 ≤ N ≤ 2,000)이 주어지고, 이어지는 N줄에 각 거주지점의 좌표가 두 개의 정수로 주어진다. 좌표의 범위는 –10⁹ 이상, 10⁹ 이하이다, 입력으로 주어지는 두 거주지점이 정확히 같은 좌표를 가지는 경우는 없다.

입력에 주어진 거주지점에 대해 도시를 가로지르는 최적의 고압선 형태에서 거주지점까지의 직선거리의 최솟값을 실수 형태로 출력하시오. 출력한 실수의 값의 절대오차 혹은 상대오차가 10^-6 이하이면 정답으로 판단한다. 참고로 절대오차는 |(출력한 값) – (정답)|을 의미하며, 상대오차는 |(출력한 값) – (정답)| / (정답)을 의미한다.