Optimal Placement for Maximum Square

Farmer John’s cows are taking part in a contest against Farmer Bob’s cows. They are placed on an $N \times N$ square lattice (with points having integer coordinates from 0 to $N-1$) and no two cows share the same point. Each farm aims to form a square with maximum area using four of its cows as vertices (the square does not have to be axis‐aligned). All of John’s cows are already placed on the grid except for his prized cow, Bessie. Your task is to determine where to place Bessie (on a currently empty point) so that the maximum square (which is formed using any four of John’s cows, and Bessie does not necessarily have to be one of the square’s vertices) has the largest possible area.

We define the area of a square with side length $\sqrt{a}$ as $a$. In particular, if two points $P=(x_1,y_1)$ and $Q=(x_2,y_2)$ are adjacent vertices of a square, then the square’s area is given by: [ \text{Area} = (x_2-x_1)^2+(y_2-y_1)^2. ]

The input provides the grid size $N$, the number of John’s pre-placed cows $J$ (excluding Bessie), and the number of Bob’s cows $K$. Then follow $J$ lines of coordinates for John’s cows and $K$ lines for Bob’s cows.

Your goal is to output the maximum area of a square that can be formed (after optimally placing Bessie) using only the points occupied by John’s cows. If no square can be formed, output 0.

inputFormat

The first line contains three integers: $N$, $J$, and $K$, where $1 \leq N \leq \text{(some upper bound)}$, $J \ge 0$, and $K \ge 0$. The next $J$ lines each contain two integers $x$ and $y$ (with $0 \le x,y \le N-1$) representing the coordinates of John’s cows (excluding Bessie). The following $K$ lines each contain two integers $x$ and $y$ representing the coordinates of Bob’s cows. It is guaranteed that no point is occupied by more than one cow.

outputFormat

Output a single integer denoting the maximum area of a square that can be formed by John’s cows (after optimally placing Bessie), where the area is calculated as $$(x_2-x_1)^2+(y_2-y_1)^2$$ for any adjacent vertices of the square. If no square can be formed, output 0.

sample

3 3 1
0 0
0 1
1 0
2 2

1