Airline Hub

Interview

Time limit1sMemory limit128 MB

Summary

Given up to 1000 airports by latitude and longitude, pick the one minimizing the largest great-circle distance to any other airport, breaking ties by earliest input order.

Level: Medium4 of 10
Topics: Geometry, Brute force, Math, Implementation
Solved: No attempts yet

Problem

World Wide Flyer has landing rights at several airports around the world. They want to place their central hub at one of these airports — the airport that minimizes the maximum direct flying distance from the hub to every other airport.

Treat the Earth as a perfect sphere and take the direct flying distance between two airports to be the great-circle distance (the shortest distance along the surface). Because the sphere's radius is a positive factor common to every distance, the best hub is the airport that minimizes the largest central angle to the other airports, and the choice does not depend on the radius that is used.

Input

The first line contains an integer $n$ ( $1 \le n \le 1000$ ), the number of airports. Each of the next $n$ lines contains two real numbers: the latitude (between $-90$ and $+90$ degrees) and the longitude (between $-180$ and $+180$ degrees) of an airport.

Output

Print a single line with the latitude and longitude of the airport that best serves as the hub, each rounded to exactly two decimal places and separated by a single space. If several airports achieve the minimum possible maximum distance, print the one that appears earliest in the input.

Examples3

Example 1

Input

3
3.2 -15.0
20.1 -175
-30.2 10

Expected output

3.20 -15.00

Example 2
Input
```
5
0 0
0 10
0 20
0 30
0 40
```
Expected output
```
0.00 20.00
```

Example 3

Input

Expected output

0.00 175.00