#O1108. 平面最近点对(平方距离)
平面最近点对(平方距离)
题目描述
给定平面上 个互不相同的整点 ,求其中最近两点之间距离的平方的最小值。
输入格式
第一行一个整数 。
接下来 行,每行两个整数 。
输出格式
一行一个整数,表示最近点对距离的平方。
样例 #1
样例输入 #1
4
0 0
3 4
1 1
5 0
样例输出 #1
2
数据规模与约定
| 数据范围 | 说明 |
|---|---|
| 点数 | |
| 坐标范围 |
- 距离的平方定义为 ,结果可达 ,请使用 64 位整型。
- 输入保证所有点坐标互不相同。
给定平面上 n 个互不相同的整点 (xi,yi),求其中最近两点之间距离的平方的最小值。
第一行一个整数 n。
接下来 n 行,每行两个整数 xi,yi。
一行一个整数,表示最近点对距离的平方。
4
0 0
3 4
1 1
5 0
2
| 数据范围 | 说明 |
|---|---|
| 2≤n≤105 | 点数 |
| −109≤xi,yi≤109 | 坐标范围 |