Problem Description

After 11 years of strategic patience, a certain country has developed a new missile interception system. Any missile within its operational radius can be successfully intercepted. When the operational radius is 0, it can intercept missiles that are exactly at the same position. However, this missile interception system has a flaw: each system can only set its operational radius once per day. The cost of usage for that day is the sum of the squares of the operational radii of all systems.

One day, the radar detected incoming missiles from an enemy country. Since the system is still in the experimental phase, only two systems are operational. If the requirement is to intercept all missiles, calculate the minimum usage cost for that day.

Input Format

The first line contains 4 integers \( x_1, y_1, x_2, y_2 \), separated by spaces, indicating the coordinates of the two missile interception systems: \((x_1, y_1)\) and \((x_2, y_2)\). The second line contains an integer \( N \), indicating the number of missiles. The next \( N \) lines, each containing two integers \( x, y \), separated by a space, represent the coordinates \((x, y)\) of a missile. Different missiles may have the same coordinates.

Output Format

A single integer, the minimum usage cost for that day.

Sample Input and Output

Sample Input #1

0 0 10 0
2
-3 3
10 0

Sample Output #1

18

Sample Input #2

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

Sample Output #2

30

Notes

The squared distance between two points \((x_1, y_1)\) and \((x_2, y_2)\) is \((x_1 - x_2)^2 + (y_1 - y_2)^2\).

The sum of the squares of the operational radii \( r_1 \) and \( r_2 \) refers to the sum of \( r_1^2 \) and \( r_2^2 \).

Sample 1 Explanation

In Sample 1, to intercept all missiles with the minimum usage cost, the squares of the operational radii for the two systems are 18 and 0, respectively.

Sample 2 Explanation

In Sample 2, the positions of the missile interception systems and the missiles are shown in the following diagram. To intercept all missiles with the minimum usage cost, the squares of the operational radii for the two systems are 20 and 10, respectively.

Data Range

• For 10% of the data, \( N = 1 \).
• For 20% of the data, \( 1 \le N \le 2 \).
• For 40% of the data, \( 1 \le N \le 100 \).
• For 70% of the data, \( 1 \le N \le 1000 \).
• For 100% of the data, \( 1 \le N \le 10^5 \), and the absolute values of all coordinate components do not exceed 1000.

NOIP2010 Junior Group Problem 3

见题面 Input 部分

见题面 Output 部分