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

输入 #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

输出 #1

3 2
0 1
0 1
0 1

说明/提示

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