11276: [yosupo] Geometry - Furthest Pair of Points
[Creator : ]
Description
This problem has $T$ cases.
Given $N$ 2D points $p _ i(x _ i , y _ i)$ ($0\leq i\leq N - 1$). Find a pair $(i,j)$, such that $i\neq j$ and $\mathrm{dist}(p _ i,p _ j) = \max_{i\neq j}\mathrm{dist}(p _ i,p _ j)$.
Here, $\mathrm{dist}$ denotes the Euclidean distance between two points.
Given $N$ 2D points $p _ i(x _ i , y _ i)$ ($0\leq i\leq N - 1$). Find a pair $(i,j)$, such that $i\neq j$ and $\mathrm{dist}(p _ i,p _ j) = \max_{i\neq j}\mathrm{dist}(p _ i,p _ j)$.
Here, $\mathrm{dist}$ denotes the Euclidean distance between two points.
Input
$T$
$N$
$x_0$ $y_0$
$x_1$ $y_1$
:
$x_{N - 1}$ $y_{N - 1}$
$N$
$x_0$ $y_0$
$x_1$ $y_1$
:
$x_{N - 1}$ $y_{N - 1}$
$\vdots$
$N$
$x_0$ $y_0$
$x_1$ $y_1$
:
$x_{N - 1}$ $y_{N - 1}$
$N$
$x_0$ $y_0$
$x_1$ $y_1$
:
$x_{N - 1}$ $y_{N - 1}$
$\vdots$
Constraints
- $1\leq T\leq 10^5$
- $2 \leq N \leq 5\times 10^5$
- $|x_i|, |y_i| \leq 10^9$
- $x_i, y_i$ are integers.
- The sum of $N$ over all test cases does not exceed $5\times 10^5$
- $2 \leq N \leq 5\times 10^5$
- $|x_i|, |y_i| \leq 10^9$
- $x_i, y_i$ are integers.
- The sum of $N$ over all test cases does not exceed $5\times 10^5$
Sample 1 Input
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
Sample 1 Output
3 2
0 1
0 1
0 1