洛谷 P1429 平面最近点对(加强版)
本文最后更新于496 天前,其中的信息可能已经过时,如有错误请发送邮件到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);
}

如果觉得本文对您有所帮助,可以支持下博主,一分也是缘
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇