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 d2. 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.
The first line contains an integer N. The next N lines give co-ordinates of the N cities. The i-th line contains two real numbers xi and yi that give co-ordinates of the i-th city.
Print out the minimum sadness of the country with absolute error less than 10-6.
- 3 ≤ N ≤ 100
- 0.0 ≤ x i , y i ≤ 1000.0
Input: 4 1 1 2 2 10 0 20 0 Output: 0
The first road goes through the first two cities and the second road goes through the last two cities.
|Tags||discretization, geometry, hard, sept13, tuananh93|
|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|
Fetching successful submissions
If you are still having problems, see a sample solution here.