Background

This problem comes from the repository https://github.com/yosupo06/library-checker-problems.

Problem Description

This problem has $T$ cases.

Given $N$ 2D points $p_i (x_i, y_i)$ $(0 \le i \le N - 1)$. Find a pair $(i, j)$, such that $i \ne j$ and $\text{dist}(p_i, p_j) = \max_{i \ne j} \text{dist}(p_i, p_j)$.

Here, $\text{dist}$ denotes the Euclidean distance between two points.

Input Format

$T$
$N$
$x_0\ y_0$
$x_1\ y_1$
$\vdots$
$x_{N-1}\ y_{N-1}$
$N$
$x_0\ y_0$
$x_1\ y_1$
$\vdots$
$x_{N-1}\ y_{N-1}$
$\vdots$

4
5
-1 -1
-6 4
-9 -7
2 5
-7 6
2
1 2
3 4
3
1 1
1 1
1 1
2
-1000000000 1000000000
1000000000 -1000000000

3 2
0 1
0 1
0 1

Hint

• $1 \le T \le 10^5$
• $2 \le N \le 5 \times 10^5$
• $|x_i|, |y_i| \le 10^9$
• $x_i, y_i$ are integers
• The sum of $N$ over all test cases does not exceed $5 \times 10^5$