#O1108. 平面最近点对(平方距离)

平面最近点对(平方距离)

题目描述

给定平面上 nn 个互不相同的整点 (xi,yi)(x_i,y_i),求其中最近两点之间距离的平方的最小值。

输入格式

第一行一个整数 nn。

接下来 nn 行,每行两个整数 xi,yix_i,y_i。

输出格式

一行一个整数,表示最近点对距离的平方。

样例 #1

样例输入 #1

4
0 0
3 4
1 1
5 0

样例输出 #1

2

数据规模与约定

数据范围 说明
2≤n≤1052 \le n \le 10^5 点数
−109≤xi,yi≤109-10^9 \le x_i,y_i \le 10^9 坐标范围
  • 距离的平方定义为 (xi−xj)2+(yi−yj)2(x_i-x_j)^2+(y_i-y_j)^2,结果可达 8×10188\times10^{18},请使用 64 位整型。
  • 输入保证所有点坐标互不相同。