Clear All of Them II

Acmers have been the Earth Protector against the evil enemy for a long long time, now it’s your second turn to protect our home.
  There are 4 * n enemies in the map. Your task is to clear all of them with your super laser gun at the fixed position (x, y).
  For each laser shot, your laser beam can reflect 3 times (must be 3 times), which means it can kill 4 enemies at one time. And the energy this shot costs is the total length
of the laser path.
For example, if you are at (0, 0), and use one laser shot kills the 4 enemies in the order of (3, 4), (6, 0), (3, 0), (0, 4), then the energy this shot costs is 5.0 + 5.0 + 3.0 + 5.0
= 18. 00.
To save the energy, you decide to use the Greedy Algorithm, which means for each shot, you select four existed enemies and decide the reflect order, so that this shot’s
energy cost is minimum. If there is a tie, we assure that choosing the shot whose four enemies’ average distance to you is smallest can avoid a tie. (See the sample for
more details)
Now, telling you your position and the 4n enemies’ position, can you tell me how much energy you need in total to clear all of them?
  Note that:
   > Each enemy can only be attacked once.
   > All the positions will be unique.
   > You must attack 4 different enemies in one shot.
   > You can’t change your position.

The first line contains a single positive integer T( T <= 20 ), indicates the number of test cases.
For each case:
  There are 2 integers x and y in the first line, which means your position.
  The second line is an integer n(1 <= n <= 50), denote there are 4n enemies.
  Then there following 4n lines, each line have 2 integers denote the position of an enemy.
  All the position integers are between -1000 and 1000.

For each test case: output the case number as shown and then print a decimal v, which is the energy you need in total to clear all of them (round to 2 decimal places).

2

0 0
1
6 0
3 0
3 4
0 4

0 0
2
1 0
2 0
3 0
4 0
1 1
1 2
1 3
1 4

Case #1: 14.00
Case #2: 13.00

Case #2:
For the first shot,
(0, 0)->(1, 0)->(2, 0)->(3, 0)->(4, 0) cost 4 energy;
and (0, 0)->(1, 0)->(1, 1)->(1, 2)->(1, 3) cost 4 energy, too.
But (0, 0)->(1, 0)->(1, 1)->(1, 2)->(1, 3)’s average distance to you(0, 0) is smallest(which is about 1.9531398), so we choose (0, 0)->(1, 0)->(1, 1)->(1, 2)->(1, 3)
for the first shot.

2011 Multi-University Training Contest 9 - Host by BJTU