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

This problem comes from the repository https://github.com/yosupo06/library-checker-problems.

This problem has $T$ cases. Given $ N $ 2D points $ p_i (x_i, y_i) $ $(0 \le i \le N - 1)$. Find a pair $ (i, j) $, such that $ i \ne j $ and $ \text{dist}(p_i, p_j) = \max_{i \ne j} \text{dist}(p_i, p_j)$. Here, $\text{dist}$ denotes the Euclidean distance between two points.

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

N/A

- $ 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 $ are integers - The sum of $ N $ over all test cases does not exceed $ 5 \times 10^5 $