새로 건설하게 될 신도시에 대한 기반시설 설계가 진행중이다.

원활하고 안정적인 전력 공급을 위해 고압선을 이 도시를 가로지르도록 하기로 하였다.

하지만 고압선은 강력한 전자기장을 유도하기 때문에 거주지에서는 가능한 거리를 두고 싶다.

도시의 거주지역을 평면 상의 N개의 점으로 표현하고,

고압선은 이 평면 상에서 완전한 직선 형태를 가진다고 가정하자.

이때, 고압선까지의 거리가 가장 가까운거주지가 가장 큰 영향을 받게 되기 때문에,

최적의 고압선은 도시를 가로지르면서 도 각 거주지점까지의 직선거리의 최솟값을 최대화해야 한다.

고압선(직선)이 도시를 가로지른다는 것은 구체적으로 고압선을 기준으로

양쪽에 모두 거주지점이 하나 이상 존재한다는 것을 의미한다.

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

[부분문제의 제약 조건]

* 부분문제 1: 전체 점수 100점 중 14점에 해당하며 N = 2 혹은 N = 3이다.

* 부분문제 2: 전체 점수 100점 중 21점에 해당하며 N ≦ 50 이며, 좌표의 범위는 –1,000 이상, 1,000 이하이다. 또한 세 거주지점이 한 직선 위에 놓이는 경우는 없다.

* 부분문제 3: 전체 점수 100점 중 9점에 해당하며 N ≦ 500 이며, 좌표의 범위는 –10⁵ 이상, 10⁵ 이하이다. 또한 세 거주지점이 한 직선 위에 놓이는 경우는 없다.

* 부분문제 4: 전체 점수 100점 중 30점에 해당하며 N ≦ 2,000 이며, 좌표의 범위는 –10⁹ 이상, 10⁹ 이하이다. 또한 세 거주지점이 한 직선 위에 놓이는 경우는 없다.

* 부분문제 5: 전체 점수 100점 중 26점에 해당하며 원래의 제약조건 이외에 아무 제약조건이 없다.

고압선(powerline) timer 1초 memory 256MB

고압선(powerline) 1초 256MB