帮帮忙

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

ebubu @ 2021-06-11 14:14:13

#include<iostream>
#include<iomanip>
#include<cstdio>
#include<math.h>
#include<algorithm>
using namespace std;
const int INF = 2 << 20;
struct point
{
    double x;
    double y;
};
point p[100000];
int temp[100000];

double dist(int i, int j)
{
    double x = (p[i].x - p[j].x) * (p[i].x - p[j].x);
    double y = (p[i].y - p[j].y) * (p[i].y - p[j].y);
    return sqrt(x + y);
}

bool cmp(const point &a, const point &b)
{
    if (a.x == b.x)
        return a.y < b.y;
    else
        return a.x < b.x;
}

bool cmp2(const int& a, const int& b)
{
    return p[a].y < p[b].y;
}

double min(double a, double b)
{
    return a < b ? a : b;
}

double merge(int left, int right)
{
    double d = INF;
    if (left == right)
        return d;
    if (left + 1 == right)
        return dist(left, right);

    int mid = left+right>>1;
    double l=merge(left, mid);
    double r=merge(mid + 1, right);
    d = min(1, r);

    int i, j, k = 0;
    for (i = left; i <= right; i++)
        if (fabs(p[mid].x-p[i].x) <= d)
            temp[k++] = i;

    sort(temp, temp + k, cmp2);

    for (i = 0; i < k; i++)
        for (j = i + 1; j < k && (p[temp[j]].y - p[temp[i]].y) < d; j++)
        {
            double m = dist(temp[i], temp[j]);
            if (d > m)
                d = m;
        }
    return d;
}

int main()
{
    int n;
    cin >> n;

    for (int i = 0; i < n; i++)
        cin >> p[i].x >> p[i].y;

    sort(p, p + n, cmp);

    printf("%.4lf\n", merge(0, n - 1));

}

我感觉没错啊 但是代码过不了 帮帮忙


by 阿丑 @ 2021-06-11 14:17:03

主页双帖,___


|