分治91分,第二个点WA求助

P1429 平面最近点对(加强版)

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;
}

|