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

1397. Points Game

Time limit: 1.0 second
Memory limit: 64 MB
Two students are playing the following game. There are 2·n points on the plane, given with their coordinates (xiyi). Each move player paints the point with his own color (first with white, second with black). The first student makes odd moves, second student makes even moves. When all points are painted (each student made n moves), the game finishes. Each student gets amount of points (real number) that equals to the sum of all distances among pairs of points, colored with his color. Student who get more points becomes a winner. The students play optimally. Find and print the difference between points amount of winner and looser.

Input

Contains multiple test cases. The first line of each case contains positive integer number n (n ≤ 500). Next 2·n lines contain points' coordinates (x1, y1), (x2, y2), …, (x2n, y2n).

Output

For each test case output the difference between the points of winner and looser. Output the difference with three digits after decimal point.

Sample

inputoutput
2
0 0
0 1
1 0
1 1
2
0 0
1 0
0 3
1 5
0.000
1.937
Problem Author: Michael Medvedev
Problem Source: Open All-Ukrainian Collegiate Programming Contest 2006