P1429 平面最近点对（加强版） – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目背景

P7883 平面最近点对（加强加强版）

题目描述

给定平面上 n 个点，找出其中的一对点的距离，使得在这 n 个点的所有点对中，该距离为所有点对中最小的

输入格式

第一行：n ，保证 2<=n<=200000 。

接下来 n 行：每行两个实数：x y，表示一个点的行坐标和列坐标，中间用一个空格隔开。

输出格式

仅一行，一个实数，表示最短距离，精确到小数点后面 4 位。

样例 #1

样例输入 #1

3
1 1
1 2
2 2

样例输出 #1

1.0000

提示

数据保证 0<= x,y<= 10^9

思路

对于两个距离比较近的点来说，两个点与原点的距离一定不会差太多。

所以我们可以根据该点与原点的距离进行排序，每次计算两个点的距离都只从该点到该点往后的5-10个点进行计算

点与原点的距离为：r=sqrt(x²+y²);sqrt()函数一般效率比较差，由于我们只是用于排序，所以我们直接用r²就行

代码

#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
using namespace std;
int n;
double ans=1e15;
struct node
{
	double x, y, r;
	node()
	{
		x = 0;
		y = 0;
		r = 0;
	}
}a[200005];
bool cmp(node a, node b)
{
	return a.r < b.r;
}
double dis(node a, node b) {
	return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));//计算两点之间距离 
}
int main()
{
	cin >> n;
	for (int i=0;i<n;i++)
	{
		cin >> a[i].x >> a[i].y;
		a[i].r = a[i].x * a[i].x + a[i].y * a[i].y;
	}
	sort(a, a + n, cmp);
	for (int i = 0; i < n; i++)
	{
		for (int j = 1; j <= 5 && i + j < n; j++)
		{
			double t = dis(a[i], a[i + j]);
			ans = min(ans, t);
		}
	}
	printf("%.4lf", ans);
}