WA了求教大佬

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

低焓体 @ 2019-02-10 21:58:24

#include <iostream>
#include <iomanip>
#include <cmath>

using namespace std;
const double INF = 1e20;
struct Point {
    double x, y;

    bool operator<(Point &pt) {
        if (x == pt.x) return y < pt.y;
        else return x < pt.x; 
    }

    bool operator>(Point &pt) {
        return !(*this < pt);
    }
};
Point pset[200005];
int near[200005], nearn;
int psetn, hn;

inline void swap(Point &p1, Point &p2)
{
    Point pt;
    pt = p1;
    p1 = p2;
    p2 = pt;
}

void push(Point x)
{
    pset[++hn] = x;
    int p = hn, f;
    while (p >= 2) {
        f = p >> 1;
        if (pset[f] > pset[p]) break;
        swap(pset[f], pset[p]);
        p = f;
    }
}

void pop()
{
    swap(pset[1], pset[hn--]);
    int p = hn, k, mhn = hn << 1;
    while (p <= mhn) {
        k = p << 1;
        if (k + 1 <= hn && pset[k + 1] > pset[k]) k++;
        if (pset[p] > pset[k]) break;
        swap(pset[p], pset[k]);
        p = k;
    }
}

void hsort()
{
    for (int i = 1; i <= psetn; i++) push(pset[i]);
    for (int i = 1; i <= psetn; i++) pop();
}

inline double min(double d1, double d2)
{
    return d1 < d2 ? d1 : d2;
}

inline double sqr(double x)
{
    return x * x;
}

inline double dis2(Point &p1, Point &p2)
{
    return sqr(p1.x - p2.x) + sqr(p1.y - p2.y);
}

double dc(int l, int r)
{
    double mdis = INF;
    if (l == r) return mdis;

    int mid = (l + r) >> 1;
    mdis = min(dc(l, mid), dc(mid + 1, r));

    for (int i = l; i <= r; i++)
        if (sqr(pset[i].x - pset[mid].x) < mdis) near[++nearn] = i;

    for (int i = 1; i < nearn; i++)
        for (int j = i + 1; j <= nearn && sqr(pset[i].y - pset[j].y) < mdis; j++)
            mdis = min(mdis, dis2(pset[near[i]], pset[near[j]]));

    nearn = 0;
    return mdis;
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> psetn;
    for (int i = 1; i <= psetn; i++)
        cin >> pset[i].x >> pset[i].y;

    hsort();
    cout << fixed << setprecision(4) << sqrt(dc(1, psetn));

    return 0;
}

by 白菜道士 @ 2019-07-11 14:55:59

看不懂你写的 看这个


by 白菜道士 @ 2019-07-11 15:05:36

@dihanti 真的看不懂你写的,我理解能力太差,qwq.


|