항공사 허브

면접 대비

시간 제한1초메모리 제한128 MB

요약

위도와 경도로 주어진 최대 1000개의 공항 중 다른 모든 공항까지의 대원 거리 최댓값이 가장 작은 공항을 고르고, 동률이면 입력 순서가 빠른 것을 출력한다.

난이도: 보통10점 중 4점
유형: 기하, 완전 탐색, 수학, 구현
정답자: 아직 제출이 없습니다

문제

World Wide Flyer는 전 세계 여러 공항에 취항 권한을 가지고 있다. 이들은 중앙 허브를 이 공항들 중 하나에 두려는데, 허브에서 다른 모든 공항까지의 직항 비행 거리 중 최댓값이 최소가 되는 공항을 고르려 한다.

지구는 완전한 구라고 가정하고, 두 공항 사이의 직항 비행 거리는 대권 거리(구 표면을 따라가는 최단 거리)로 정의한다. 구의 반지름은 모든 거리에 공통으로 곱해지는 양수이므로, 최적의 허브는 다른 공항들까지의 중심각 중 최댓값을 최소로 만드는 공항이며 반지름 값과 무관하다.

입력

첫 번째 줄에 공항의 수 $n$ ( $1 \le n \le 1000$ )이 주어진다. 이어지는 $n$ 개의 줄에는 각각 한 공항의 위도(latitude, $-90$ 도 이상 $+90$ 도 이하)와 경도(longitude, $-180$ 도 이상 $+180$ 도 이하)가 실수로 주어진다.

출력

허브로 가장 적합한 공항의 위도와 경도를 한 줄에 출력한다. 각 값은 소수점 아래 둘째 자리까지 반올림하여 공백 하나로 구분해 출력한다. 최대 거리의 최솟값을 달성하는 공항이 여러 개라면, 입력에서 가장 먼저 나오는 공항을 출력한다.

예제3

예제 1

입력

3
3.2 -15.0
20.1 -175
-30.2 10

예상 출력

3.20 -15.00

예제 2
입력
```
5
0 0
0 10
0 20
0 30
0 40
```
예상 출력
```
0.00 20.00
```

예제 3

입력

예상 출력

0.00 175.00