平面最近点对
题号:NC249607
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

给定 n 个二维欧几里得平面上的点 p_1, p_2, \dots, p_n,请输出距离最近的两个点的距离。

输入描述:

输入第一行为一个正整数 T (1 \leq T \leq 4 \cdot 10^5),表示数据组数。

对于每组数据:

第一行输入一个整数 n (1 \leq n \leq 4 \cdot 10^5),表示点数。

接下来 n 行,第 i 行为用空格隔开的整数 x_i, y_i (-10^7 \leq x_i,y_i \leq 10^7),表示 p_i = (x_i, y_i)

输入保证:没有两个坐标完全相同的点。

保证 \sum n \leq 4 \cdot 10^5

输出描述:

输出一行,包含一个整数 D^2,表示距离最近的两个点的距离的平方。

由于输入的点为整点,因此这个值一定是整数。
示例1

输入

复制
2
2
-10000000 -10000000
10000000 10000000
5
1 1
1 9
9 1
9 9
0 10

输出

复制
800000000000000
2

备注:

原题链接:https://www.luogu.com.cn/problem/P7883