
ZOJ Problem Set  4083
Little Sub is happy to see that you solve his geometry problem quickly, so he comes with another geometry problem for you as the reward. Given a 2dimensional space described as $\{(x,y)0 \le x\le M,0\le y\le M\}$ and $N$ points $P_1(x_1,y_1), P_2(x_2,y_2), \dots, P_N(x_N,y_N)$ (note that different points may share the same coordinate), we define a "good square" as a square inside the given 2dimensional space such that the edges of the square is parallel to the xaxis or the yaxis, and none of the given $N$ points are strictly inside it. You're also given $Q$ queries. In each query, given a coordinate $(u,v)$, please calculate that the largest area of a good square such that $(u,v)$ is strictly inside.InputThere are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 10$), indicating the number of test cases. For each test case: The first line contains two integers $M$ (${2\leq M\leq 10^9}$) and $N$ (${0\leq N\leq 5000}$), indicating the range of the given 2dimensional space and the number of the given points. For the following $N$ lines, the $i$th line contains two integers $X_i$ and $Y_i$ (${0\le X_i,Y_i\le M}$), indicating the Euclidean coordinate of the $i$th point. The next line contains one integer $Q$ (${1\leq Q\leq 5000}$), which denotes the number of queries. In the following $Q$ lines, each line contains two integers $u$ and $v$(${0\le u,v\le M})$, indicating a query. OutputFor each query, output an integer in one line representing the answer. Sample Input1 5 5 1 4 2 1 3 2 4 1 4 4 3 3 1 2 3 4 3 Sample Output4 9 4 HintWe now illustrates the second query of the sample input below. Author: LIU, Zhengze Source: ZOJ Monthly, January 2019 