Big Circle

Time limit1sMemory limit16 MB

Summary

Given up to 100000 points on a single circle, find the smallest Euclidean distance between any two of them.

Level: Medium6 of 10
Topics: Geometry, Sorting
Solved: No attempts yet

Problem

At a World Cup opening ceremony, children from around the world tried to form a big circle on the field. They succeeded in making a perfect circle, but because they had not practiced much, the kids were not evenly spaced. Find the minimum Euclidean distance between any two kids.

Input

The first line contains an integer $N$ , the number of kids. Each of the next $N$ lines contains two real numbers, rounded to two decimal places, giving the coordinates of one kid.

It is guaranteed that all points lie on one circle.

Output

Print one real number, rounded to two decimal places: the minimum Euclidean distance between two kids.

Constraints

$2 \le N \le 10^5$
Every coordinate lies in $[-10^6, 10^6]$ .

Examples5

Example 1

Input

5
1.00 4.00
-0.50 -1.60
4.00 1.00
3.12 3.12
-1.60 -0.50

Expected output

1.56

Example 2
Input
```
2
0.00 1.00
0.00 -1.00
```
Expected output
```
2.00
```

Example 3

Input

3
1.00 0.00
-0.50 0.87
-0.50 -0.87

Expected output

1.73

Example 4

Input

4
1.00 0.00
0.00 1.00
-1.00 0.00
0.00 -1.00

Expected output

1.41

Example 5

Input

6
2.00 0.00
1.00 1.73
-1.00 1.73
-2.00 0.00
-1.00 -1.73
1.00 -1.73

Expected output

2.00