ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

2154. Flight on a Cannonball

Time limit: 2.0 second
Memory limit: 256 MB
Baron Munchausen is participating in a battle. It’s occurring on a plane with a Cartesian coordinate system. He is ordered to move to the center of the coordinate system. It’s quite simple to do: he just needs to mount a cannonball and jump off of it as close to the center as possible.
There are n cannons on the battlefield, Munchausen is near one of them. Cannons are considered as points, i-th point has coordinates (xi, yi). Being near one of the cannons, Baron can shoot in the direction of any other cannon and mount the cannonball. He cannot miss the cannon: that would damage his reputation. The cannonball flies in a straight line and never stops, even after reaching the targeted cannon. Flying over any cannon, Munchausen can dismount the cannonball and shoot in the direction of any other cannon again. This way he can freely move from cannon to cannon.
When Baron decides that he is close to the center of the coordinate system, he will dismount the cannonball and walk to the center on foot. Find the smallest possible distance Baron Munchausen would need to walk on foot.

Input

The first line contains one integer n (2 ≤ n ≤ 105) — amount of cannons.
Next n lines each contain two integers xi and yi (−105xi, yi ≤ 105) — coordinates of a cannon. It is guaranteed that no two cannons are located at the same point.

Output

Output one real number — the smallest possible distance that Baron Munchausen will walk by foot after traveling by cannonballs. Your answer is considered correct if its absolute or relative error doesn’t exceed 10−6.

Samples

inputoutput
4
1 0
0 1
-1 0
0 -1
0.0000000000
5
0 3
1 2
1 3
1 4
2 3
0.7071067812

Notes

Illustration of the second example:
Problem illustration
Problem Author: Valentin Zuev
Problem Source: Ural School Programming Contest 2020