Another Contest 8 Problem 6 - Unnecessary Forced Reverse Trash Finesse

View as PDF

Submit solution

Points: 25
Time limit: 0.5s
Memory limit: 64M

Problem type

Brandon is cleaning his room. He has N identical-looking pusheens lying in various locations on the room. No two pusheens are at the same location.

One day, Brandon draws a line cutting his room perfectly in half. He wants to arrange the pusheens in a way where, if there is a pusheen at some location (x, y) where x \neq 0, there is a different pusheen at (-x, y). This is unnecessary, of course - Brandon doesn't have to arrange his pusheens in this fashion. However, he feels forced to arrange his pusheens in this way. If someone accidentally trashes one of his pusheens, he will be able to reconstruct where the pusheen goes. Of course, if a pusheen is on the line x=0, then the location cannot be reconstructed exactly, but this is not a critical situation.

Brandon is very lazy, so moving a pusheen from (a, b) to (c, d) requires effort equal to \sqrt{(a-c)^2 + (b-d)^2}. Compute the minimum sum of efforts Brandon must exert in order to achieve his desired balanced pusheen layout.

It is not permitted to have more than one pusheen at any given point.


1 \le N \le 500

|x_i|, |y_i| \le 10^3

No two pusheens will start at the same point.

Input Specification

The first line contains a single positive integer, N.

The next N lines each contain two space-separated integers, x_i and y_i, indicating the location of the ith pusheen.

Output Specification

Output the minimum effort Brandon must exert. Your answer will be considered correct if it has absolute or relative error of at most 10^{-6} when compared with the reference answer.

Sample Input 1

-1 1
2 2

Sample Output 1


Sample Input 2

-1 39
1 39
2 3

Sample Output 2



There are no comments at the moment.