Cover The Enemy

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65535/32768 K (Java/Others)

Description

  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.

Input

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

Output

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

Sample Input

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

Sample Output

18 30

Hint

lcy

Source

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

提交代码