Total Circle

Time limit1sMemory limit256 MB

Summary

Given point sets P and Q, find the largest squared radius among centers in Q whose minimum enclosing circle of P is as small as possible.

Level: Medium7 of 10
Topics: Geometry, Brute force, Math, Binary search
Solved: No attempts yet

Problem

On the coordinate plane there are point arrays $P = P_1, P_2, \cdots, P_N$ and $Q = Q_1, Q_2, \cdots, Q_M$ . Consider a circle centered at a point of $Q$ that contains every point of $P$ , and take the one with the smallest area. Find the maximum possible radius of such a circle.

Input

The first line gives $N$ and $M$ . ($1 \le N, M \le 1000)

The next $N$ lines give $x$ and $y$ , meaning $P_i = (x, y)$ . ($-10^6 \le x, y \le 10^6)

The next $M$ lines give $x$ and $y$ , meaning $Q_i = (x, y)$ . ($-10^6 \le x, y \le 10^6)

Output

Print the square of the maximum possible radius of a smallest-area circle that is centered at a point of $Q$ and contains every point of $P$ .

Examples2

Example 1
Input
```
1 1
0 0
1000000 1000000
```
Expected output
```
2000000000000
```
Example 2
Input
```
4 4
2 6
3 1
1 7
8 9
4 3
5 2
9 6
6 4
```
Expected output
```
65
```