Two Roads

All submissions for this problem are available.
Byteland is notorious for its poor transportation system. There are N villages located far away from each other. So the only way of going from one village to another is using the narrow pathways. But now it's time to make some changes. People in Byteland are going to improve the transportation system in their own way. They have planned to build two straight roads. These roads will not necessary connect any cities but they should decrease the time of traveling between some cities. People can use a pathway to go from one city to the nearest point on the road. Then they can move [along the road] to the point of the road that is the nearest to their destination. And finally, they can use another pathway to move from that point to the destination.
Let d be the distance from the city to the closest point that belongs to one of the roads, then the sadness of that city will be equal to d^{2}. The sadness of the whole country is the average of the sadness of all cities. Can you help Byteland to find the plan that will minimize the sadness of the country? You can assume that:
 The cities are considered to be points on the plane and the roads are considered to be line segments.
 A road can have arbitrary length if that reduces the sadness of the country.
 The two roads may have a common point.
 A road can go through some cities (so the distance from these cities to the road is 0).
 No 3 or more cities lie on the same line.
Input
The first line contains an integer N. The next N lines give coordinates of the N cities. The ith line contains two real numbers x_{i} and y_{i} that give coordinates of the ith city.
Output
Print out the minimum sadness of the country with absolute error less than 10^{6}.
Constraints
 3 ≤ N ≤ 100
 0.0 ≤ x_{ i } , y_{ i } ≤ 1000.0
Example
Input: 4 1 1 2 2 10 0 20 0 Output: 0
Explanation
The first road goes through the first two cities and the second road goes through the last two cities.
Author:  tuananh93 
Tester:  xcwgf666 
Editorial  http://discuss.codechef.com/problems/TWOROADS 
Tags  discretization, geometry, hard, sept13, tuananh93 
Date Added:  1082013 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 