King's Keep

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

요약

서로 다른 점 1000개 이하가 주어질 때, 다른 점들까지의 평균 유클리드 거리가 가장 작은 점을 골라 그 평균을 출력한다.

난이도: 쉬움10점 중 3점
유형: 기하, 완전 탐색, 수학
정답자: 아직 제출이 없습니다

문제

King Carl's kingdom contains $k$ keeps (commonly called castles).

Coordinates of keeps are known, and King Carl considers himself convinced that it could be convenient to choose a central keep as King Carl's residence.

Critically, King Carl considers that the average cost to carry commands from King Carl's residence to King Carl's other keeps should be small.

Compute the minimal average Euclidean distance1 from his residence keep to the other keeps if King Carl chooses his residence optimally.

1The Euclidean distance between two points is the length of a straight line segment between these points.

입력

The input consists of:

One line with an integer $k$ ( $2\leq k\leq 1000$ ), the number of keeps.
$k$ lines, each with two integers $x$ and $y$ ( $|x|, |y| \leq 1000$ ), the coordinates of the keeps.

It is guaranteed that all keeps are at distinct locations.

출력

Output the minimal possible average distance from the keep that is chosen as the king's residence to all other keeps.

Your answer should have an absolute or relative error of at most $10^{-6}$ .

예제2

예제 1
입력
```
3
0 0
9 9
0 9
```
예상 출력
```
9
```
예제 2
입력
```
5
-3 5
6 8
1 2
5 -4
-7 -9
```
예상 출력
```
8.405705684
```