#P2189. 三维最近点对

    ID: 1213 传统题 4000ms 259MiB 尝试: 111 已通过: 10 难度: 7 上传者: 标签>CF2200提高+/省选-最近点对K-D Tree按维度中位数划分包围盒剪枝搜索顺序优化平方距离比较

三维最近点对

题目描述

给定三维空间的 nn 个点,输出 min⁡{dist⁡(i,j)∣i≠j}\min\{\operatorname{dist}(i,j) | i\neq j \}。

其中 $\operatorname{dist}(i,j)=(x_i-x_j)^2+(y_i-y_j)^2+(z_i-z_j)^2$。

输入格式

第一行一个正整数 nn。

接下来 nn 行,每行三个正整数 xi,yi,zix_i,y_i,z_i,表示每一个点的坐标。

输出格式

输出一个整数,表示两点之间的最小距离平方。不同编号的点可以拥有相同坐标。

样例输入

2
1 1 1
1 1 1

样例输出

0

数据规模与约定

对于 100%100\% 的数据,1≤xi,yi,zi≤1071\leq x_i,y_i,z_i\leq 10^7,2≤n≤1062\le n\le10^6。