Cover The Enemy

  Now, the war is coming, no one want to fight with others, but you have to when you are facing.
  As the king of a country, you should defend your country. The condition is that “There are N enemy armies around you, you have two towers and you want to build cannon on each tower to cover all the enemy armies”. The cannon has an “attack distance” R with a cost of R^2.
  You are facing a problem, to cover all the armies and make the cost R1^2 + R2^2 minimal, where R1 and R2 are the attack distance of the two towers.

The first line contains an integer t, number of test cases, following with t groups of test cases described as following.
For each case, the first line contains four integers: x1, y1, x2, y2, the Coordinates of the two towers.
The next line is an integer n, the number of enemy armies, following with n lines of coordinates: x, y, which is the coordinate of a group of enemy army, where:
  t <= 100
1 <= n <= 100000,
-1000 <= x, y <= 1000
-1000 <= x1, y1, x2, y2 <= 1000

The minimal cost of the two tower to cover all the enemy armies.

2
0 0 10 0
2
-3 3
10 0
0 0 6 0
5
-4 -2
-2 3
4 0
6 -2
9 1

18
30

mark1989@BJTU

2011百校联动“菜鸟杯”程序设计公开赛