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

Ural FU contest. Kontur Cup. Petrozavodsk training camp. Winter 2013

About     Problems     Submit solution     Judge status     Standings
Contest is over

F. Fire Signals

Time limit: 1.0 second
Memory limit: 64 MB
Captain Vrungel and his mate Lom were shipwrecked and got to an uninhabited island. While the captain sought for fresh water in the island jungle, Lom decided to make some fire signals on the beach. He wanted to burn them all at night to send a distress signal that could be seen from a ship.
When captain Vrungel returned to the beach, Lom had already made n bonfires. Captain looked at the fires and said that if one set all fires in one line they could be seen not only from a ship but from an airplane too. Find the minimal total distance, that Lom’s fire signals should be moved to, to be set in one line.

Input

First line contains an integer n that is the number of fire signals (2 ≤ n ≤ 1000). Each of the next n lines contains integers xi, yi that are the coordinates of i’th fire signal (−106xi, yi ≤ 106).

Output

Output the minimal total distance that Lom should move his fire signals to. The answer must be given with absolute or relative error not exceeding 10−6.

Sample

inputoutput
4
0 0
0 1
1 1
1 0
1.414214
Problem Author: Pavel Klimov (prepared by Olga Soboleva)
Problem Source: Ural FU contest. Kontur Cup. Petrozavodsk training camp. Winter 2013
To submit the solution for this problem go to the Problem set: 1956. Fire Signals