Doppler @ 2023-06-29 12:41:09
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 5;
struct Node
{
double x;
double y;
bool operator<(const Node &other) const
{
return x < other.x;
}
} node[N];
int n, m, xm, ym;
double mindis = 0x3f3f3f3f;
set<Node> L, R;
vector<Node> p;
bool cmp_x(const Node &n1, const Node &n2)
{
if (n1.x != n2.x)
return n1.x < n2.x;
return n1.y < n2.y;
}
bool cmp_y(const Node &n1, const Node &n2)
{
return n1.y < n2.y;
}
void update(const Node &n1, const Node &n2) // 更新最短距离
{
double dis = sqrt(pow(n1.x - n2.x, 2) + pow(n1.y - n2.y, 2));
mindis = min(mindis, dis);
}
void find_min_dis(int l, int r) // 递归分治
{
if (r - l <= 3)
{
for (int i = l; i <= r; i++)
for (int j = i + 1; j <= r; j++)
update(node[i], node[j]);
return;
}
int mid = (l + r) / 2;
find_min_dis(l, mid);
find_min_dis(mid, r);
}
void solve()
{
int i = m;
while (i >= 1 && xm - node[i].x <= mindis) // L是按x排序最中心点node[m]左侧宽度为mindis的区域,R同理
{
L.insert(node[i]);
p.push_back(node[i]);
i--;
}
i = m + 1;
while (i <= n && node[i].x - xm <= mindis)
{
R.insert(node[i]);
p.push_back(node[i]);
i++;
}
sort(p.begin(), p.end(), cmp_y); // 按y排序LR的合集
int sz = p.size();
for (int i = 0; i < sz; i++)
{
if (L.find(p[i]) != L.end()) // 对L内的点进行遍历,计算在R内的和该点高度上下4个的点的mindis
{
int up = 0, down = 0;
int iu = i, id = i; // i_up, i_down
while (down < 4 && id >= 0)
{
id--;
if (R.find(p[id]) != R.end())
update(p[i], p[id]), down++;
}
while (up < 4 && iu < sz)
{
iu++;
if (R.find(p[iu]) != R.end())
update(p[i], p[iu]), up++;
}
}
}
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> node[i].x >> node[i].y;
sort(node + 1, node + n + 1, cmp_x); // 按x排序,选取中心点
m = (n + 1) / 2;
xm = node[m].x;
find_min_dis(1, n);
solve();
cout << fixed << setprecision(4) << mindis << endl;
return 0;
}
只有个二个点WA了,而且为什么如果我把结构体和cmp比较函数改成下面这样会编译失败呢,我看dalao们都没有这个问题啊,我这里只能重载<符号(报错invalid operands to binary expression ('const Node' and 'const Node') )?
struct Node
{
double x;
double y;
} node[N];
bool cmp_x(Node n1, Node n2)
{
if (n1.x != n2.x)
return n1.x < n2.x;
return n1.y < n2.y;
}
bool cmp_y(Node n1, Node n2)
{
return n1.y < n2.y;
}