TopCoder

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

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) = \min_ {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

4 1
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}$

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 2097152 2097152
1 5000 2097152 2097152
2 5000 2097152 2097152
3 5000 2097152 2097152
4 5000 2097152 2097152
5 5000 2097152 2097152
6 5000 2097152 2097152
7 5000 2097152 2097152
8 5000 2097152 2097152
9 5000 2097152 2097152
10 5000 2097152 2097152
11 5000 2097152 2097152
12 5000 2097152 2097152
13 5000 2097152 2097152
14 5000 2097152 2097152
15 5000 2097152 2097152
16 5000 2097152 2097152
17 5000 2097152 2097152
18 5000 2097152 2097152
19 5000 2097152 2097152
20 5000 2097152 2097152
21 5000 2097152 2097152
22 5000 2097152 2097152
23 5000 2097152 2097152
24 5000 2097152 2097152
25 5000 2097152 2097152
26 5000 2097152 2097152
27 5000 2097152 2097152
28 5000 2097152 2097152