关于本题KDT解法的估价函数

Bodhi @ 2024-02-19 22:25:21

double possibleans(int u)
{ // 当前点nw到u的子树区域的最小可能距离
    if (!u)
        return 4e18;
    double s = 0;
    for (int i = 0; i < 2; ++i)
    {
        double x = max(t[nw].p[i] - t[u].mx[i], 0.0) + max(t[u].mn[i] - t[nw].p[i], 0.0);
        s += x * x;
    }
    return s;
}

by Bodhi @ 2024-02-20 20:07:07

做完P7883明白了

有一篇题解是这样写的：

inline ll H(Node t, Point p){
    auto sqr=[](int x) -> ll{return 1LL*x*x;};

    ll x=p.x[0], y=p.x[1];
    ll res=0;
    if(x<t.L[0]) res+=sqr(x-t.L[0]);
    if(x>t.R[0]) res+=sqr(x-t.R[0]);
    if(y<t.L[1]) res+=sqr(y-t.L[1]);
    if(y>t.R[1]) res+=sqr(y-t.R[1]);
    return res;
}

如何求可能的最小距离？如果这个点在矩形框内，可能距离是0，所以res默认是0；如果在框外，那就计算离这个点最近的边框的距离

此贴结