本文最后更新于548 天前,其中的信息可能已经过时,如有错误请发送邮件到1739584917@qq.com
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(x2+y2);sqrt()函数一般效率比较差,由于我们只是用于排序,所以我们直接用r2就行
代码
#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);
}