3756 . [模板題] Furthest Pair of Points
TopCoder
Tags
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.
Input Format
$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$
Output Format
Sample Input 1
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 Output 1
3 2 0 1 0 1 0 1
Hints
- $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}$
Problem Source
Subtasks
| No. | Testdata Range | Score |
|---|