最近点对

【题目描述】

本题包含 $T$ 组测试数据。

给定 $N$ 个二维平面上的点 $p_i(x_i,y_i)$（$0\leq i\leq N-1$）。请找出一对 $(i,j)$，满足 $i\neq j$ 且

其中，$\mathrm{dist}$ 表示两个点之间的欧几里得距离。

【输入】

$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$

【输出】

对于每组测试数据，输出两个整数 $i$ 和 $j$，表示一对最近点的下标。下标从 $0$ 开始。

【输入样例】

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

【输出样例】

4 1
0 1
0 1
0 1

【数据范围】

• $1\leq T\leq 10^5$
• $2 \leq N \leq 500000$
• $|x_i|, |y_i| \leq 1000000000$
• $x_i, y_i$ 为整数。
• 所有测试数据的 $N$ 之和不超过 $500000$

【来源】

Library Checker（yosupo06） closest_pair

本题为 special judge（输出任意合法解），暂不可本地评测。