410038: GYM103921 J Rock Balancing

Daniel RuLasso has acquired a large circular platform that he intends to place in the middle of a lake, and has a collection of $$$N$$$ equally weighted rocks (treated as points on the 2D plane) that he wishes to arrange on the platform for decoration. He figures that he can kill two birds with one stone by assigning the task to Kobra Cai students. As all the rocks are conveniently already on the platform, Daniel asks the students to move the rocks into a balanced state on the platform for a more aesthetically pleasing setup.

The platform is centered at the origin of the 2D plane and has infinite radius. An arrangement of rocks on the platform is considered balanced if it will not cause the platform to capsize once placed in water; this requires every rock at $$$(x, y)$$$ to be matched with a corresponding rock that is symmetric about the origin (possibly itself). Multiple rocks can be placed at the same location. However, moving any rock from $$$(a, b)$$$ to $$$(c, d)$$$ requires $$$\left(|a-c|^2 + |b-d|^2\right)$$$ energy units. The Kobra Cai students want to minimize the total energy units expended to achieve a balanced arrangement, and would like to know the minimum amount of energy units needed to do so.

The first line of input contains a single integer $$$N$$$ ($$$1 \leq N \leq 20$$$), representing the number of rocks on the platform. The next $$$N$$$ lines of input contain two integers $$$x, y$$$ ($$$0 \leq |x|, |y| \leq 10^4$$$) representing the current position $$$(x, y)$$$ of a rock.

Output the total amount of energy units necessary to move the $$$N$$$ rocks into a balanced arrangement. Any answer within $$$10^{-6}$$$ of the true solution will be accepted.

2
-1 1
1 1

2.0000000000

1
3 4

25.0000000000

For the first case, both rocks can be moved onto the $$$x$$$-axis.

For the second case, the sole rock just needs to be moved to the origin.