문제
새로 건설하게 될 신도시에 대한 기반시설 설계가 진행중이다.
원활하고 안정적인 전력 공급을 위해 고압선을 이 도시를 가로지르도록 하기로 하였다.
하지만 고압선은 강력한 전자기장을 유도하기 때문에 거주지에서는 가능한 거리를 두고 싶다.
도시의 거주지역을 평면 상의 N개의 점으로 표현하고,
고압선은 이 평면 상에서 완전한 직선 형태를 가진다고 가정하자.
이때, 고압선까지의 거리가 가장 가까운거주지가 가장 큰 영향을 받게 되기 때문에,
최적의 고압선은 도시를 가로지르면서 도 각 거주지점까지의 직선거리의 최솟값을 최대화해야 한다.
고압선(직선)이 도시를 가로지른다는 것은 구체적으로 고압선을 기준으로
양쪽에 모두 거주지점이 하나 이상 존재한다는 것을 의미한다.
최적의 고압선 형태를 계산하고 이때의 각 거주지점까지의 직선거리의 최솟값을출력하는 프로그램을 작성하시오.
[부분문제의 제약 조건]
* 부분문제 1: 전체 점수 100점 중 14점에 해당하며 N = 2 혹은 N = 3이다.
* 부분문제 2: 전체 점수 100점 중 21점에 해당하며 N ≦ 50 이며, 좌표의 범위는 –1,000 이상, 1,000 이하이다. 또한 세 거주지점이 한 직선 위에 놓이는 경우는 없다.
* 부분문제 3: 전체 점수 100점 중 9점에 해당하며 N ≦ 500 이며, 좌표의 범위는 –105 이상, 105 이하이다. 또한 세 거주지점이 한 직선 위에 놓이는 경우는 없다.
* 부분문제 4: 전체 점수 100점 중 30점에 해당하며 N ≦ 2,000 이며, 좌표의 범위는 –109 이상, 109 이하이다. 또한 세 거주지점이 한 직선 위에 놓이는 경우는 없다.
* 부분문제 5: 전체 점수 100점 중 26점에 해당하며 원래의 제약조건 이외에 아무 제약조건이 없다.
입력
표준 입력으로 다음 정보가 주어진다.
첫 번째 줄에 신도시의 거주지점의 개수 N ( 2 ≦ N ≦ 2,000 ) 이 주어지고, 이어지는 N줄에 각 거주지점의 좌표가 두 개의 정수로 주어진다. 좌표의 범위는 –109이상, 109 이하이다.
력으로 주어지는 두 거주지점이 정확히 같은 좌표를 가지는 경우는 없다.
출력
표준 출력으로 입력에 주어진 거주지점에 대해 도시를 가로지르는 최적의 고압선 형태에서 거주지점까 지의 직선거리의 최솟값을 실수 형태로 출력하시오.
출력한 실수의 값의 절대오차 혹은 상대오차가 10-6 이하이면 정답으로 판단한다. 참고로 절대오차는 |(출력한 값) – (정답)|을 의미하며, 상대오차는 |(출력한 값) – (정답)| / (정답)을 의미한다.
예제1
4
00
11
01
10
0.50000000
예제2
10
-35
00
-16
08
82
40
7-2
26
91
92
2.66789187