社区讨论

建议降绿

P1429平面最近点对(加强版)参与者 3已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@mix32y6g
此快照首次捕获于
2025/12/08 19:44
2 个月前
此快照最后确认于
2025/12/08 19:54
2 个月前
查看原帖
rt
CPP
#include <bits/stdc++.h>
using namespace std;

struct Node
{
	double x,y;
	bool operator<(Node a){return x < a.x;}
}a[210000],c[210000];
int n;

double stove(int l,int r)
{
	if(l == r) return 1e10;
	int m = (l + r) / 2;
	double d = min(stove(l,m),stove(m + 1,r));
	int cnt = 0;
	for(int i = l;i <= r;i++)
	{
		if(abs(a[i].x - a[m].x) < d)
		{
			cnt++;
			c[cnt].x = a[i].y;
			c[cnt].y = a[i].x;
		}
	}
	sort(c + 1,c + cnt + 1);
	for(int i = 1;i <= cnt;i++)
	{
		for(int j = i + 1;j <= cnt;j++)
		{
			d = min(d,sqrt((c[j].x - c[i].x) * (c[j].x - c[i].x) + (c[j].y - c[i].y) * (c[j].y - c[i].y)));
		}
	}
	return d;
}

int main()
{
	cin >> n;
	for(int i = 1;i <= n;i++) cin >> a[i].x >> a[i].y;
	sort(a + 1,a + n + 1);
	cout << fixed << setprecision(4) << stove(1,n);
}
此代码可通过此题,不开O2也跑得飞快(最慢的连500ms都没到)且几乎每有什么难点

回复

4 条回复,欢迎继续交流。

正在加载回复...