P16223 【模板】旋转卡壳/最远点对

本题来自 https://github.com/yosupo06/library-checker-problems.

本题含有 $T$ 组数据。 给出二维平面上的 $N$ 个点 $p_i(x_i,y_i)$（$0\le i\le N-1$）。你需要找到一对下标 $(i,j)$，满足 $i\ne j$ 且 $\operatorname{dist}(p_i,p_j)=\max_{i\ne j}\operatorname{dist}(p_i,p_j)$。 此处 $\operatorname{dist}$ 意为欧几里得距离。

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

对于每组数据，你需要输出一行两个整数，表示 $i$ 和 $j$。

- $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$ 均为整数； - 所有测试点中 $N$ 的总和不超过 $5 \times 10^5$。