最近点对问题 POJ 3714 Raid && HDOJ 1007 Quoit Design

题意：有n个点，问其中某一对点的距离最小是多少

分析：分治法解决问题：先按照x坐标排序，求解(left, mid)和(mid+1, right)范围的最小值，然后类似区间合并，分离mid左右的点也求最小值

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

const int N = 1e5 + 5;
const double INF = 1e100;
struct Point {
    double x, y;
    bool flag;
    bool operator < (const Point &rhs) const {
        return x < rhs.x;
    }
};
Point point[N*2];
int idy[N*2];
int n;

bool cmp_y(int i, int j) {
    return point[i].y < point[j].y;
}

double squ(double x) {
    return x * x;
}

double get_dist(Point &a, Point &b) {
    if (a.flag == b.flag) {
        return INF;
    }
    return sqrt (squ (a.x - b.x) + squ (a.y - b.y));
}

double min_dist(int left, int right) {
    if (left == right) {
        return INF;
    }
    else if (right - left == 1) {
        return get_dist (point[left], point[right]);
    } else {
        int mid = left + right >> 1;
        double ret = std::min (min_dist (left, mid), min_dist (mid + 1, right));
        if (ret == 0) {
            return ret;
        }
        int endy = 0;
        for (int i=mid; i>=left&&point[mid].x-point[i].x<=ret; --i) {
            idy[endy++] = i;
        }
        for (int i=mid+1; i<=right&&point[i].x-point[mid+1].x<=ret; ++i) {
            idy[endy++] = i;
        }
        std::sort (idy, idy+endy, cmp_y);
        for (int i=0; i<endy; ++i) {
            for (int j=i+1; j<endy&&point[j].y-point[i].y<ret; ++j) {
                ret = std::min (ret, get_dist (point[i], point[j]));
            }
        }
        return ret;
    }
}

int main() {
    int T; scanf ("%d", &T);
    while (T--) {
        scanf ("%d", &n);
        for (int i=0; i<2*n; ++i) {
            scanf ("%lf%lf", &point[i].x, &point[i].y);
            if (i < n) {
                point[i].flag = false;
            } else {
                point[i].flag = true;
            }
        }
        std::sort (point, point+2*n);
        printf ("%.3f
", min_dist (0, 2 * n - 1));
    }

    return 0;
}

HDOJ 1007

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

const int N = 1e5 + 5;
const double INF = 1e100;
struct Point {
    double x, y;
};
Point point[N], py[N];
int n;

bool cmp_x(const Point &a, const Point &b) {
    return a.x < b.x;
}
bool cmp_y(const Point &a, const Point &b) {
    return a.y < b.y;
}

double squ(double x) {
    return x * x;
}

double get_dist(Point &a, Point &b) {
    return sqrt (squ (a.x - b.x) + squ (a.y - b.y));
}

double min_dist(int left, int right) {
    if (left + 1 == right) {
        return get_dist (point[left], point[right]);
    } else if (left + 2 == right) {
        return std::min (get_dist (point[left], point[left+1]), 
                std::min (get_dist (point[left], point[right]), get_dist (point[left+1], point[right])));
    } else {
        int mid = left + right >> 1;
        double ret = std::min (min_dist (left, mid), min_dist (mid + 1, right));
        int cnt = 0;
        for (int i=mid; i>=left&&point[mid].x-point[i].x<=ret; --i) {
            py[cnt++] = point[i];
        }
        for (int i=mid+1; i<=right&&point[i].x-point[mid+1].x<=ret; ++i) {
            py[cnt++] = point[i];
        }
        std::sort (py, py+cnt, cmp_y);
        for (int i=0; i<cnt; ++i) {
            for (int j=i+1; j<cnt&&py[j].y-py[i].y<ret; ++j) {
                ret = std::min (ret, get_dist (py[i], py[j]));
            }
        }
        return ret;
    }
}

int main() {
    while (scanf ("%d", &n) == 1) {
        if (!n) {
            break;
        }
        for (int i=0; i<n; ++i) {
            scanf ("%lf%lf", &point[i].x, &point[i].y);
        }
        std::sort (point, point+n, cmp_x);
        printf ("%.2f
", min_dist (0, n - 1) / 2);
    }

    return 0;
}

最近点对问题 POJ 3714 Raid && HDOJ 1007 Quoit Design

相关推荐