社区讨论
建议降绿
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 条回复,欢迎继续交流。
正在加载回复...