AC了,但不清楚为什么AC
查看原帖
AC了,但不清楚为什么AC
1290896
WwwHx楼主2024/11/21 20:49
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

//两点之间的距离
double distance(const pair<double, double>& a, const pair<double, double>& b) {
    return sqrt((a.first - b.first) * (a.first - b.first) +
        (a.second - b.second) * (a.second - b.second));
}

//分治策略
double dfs(
    const vector<pair<double, double>>& sortOfx,
    int n, int l, int r) {
    //最小域为一个点或者两个点
    if (l == r || l > r)return INT_MAX;  //同一个点不存在距离或者此域里没有点存在
    if (l + 1 == r)return distance(sortOfx[l],sortOfx[r]);  //相邻的点求出距离

    // 1.寻找x的中点,将其分为两个域
    int mid = l + ((r - l) >> 1);

    double minr = dfs(sortOfx,  n, mid, r);
    double minl = dfs(sortOfx,  n, l, mid - 1);

    double finalyMin = min(minl, minr);     //合并两个域的最小值

    //2.求连通域的最小值    l保存左域的值 r保存右域的值     
    int temp[n], k = 0;
    for (int i = l;i <= r;i++)if (fabs(sortOfx[i].first - sortOfx[mid].first) < finalyMin)temp[k++] = i;
    
    for (int i = 0;i < k;i++) {
        for (int j = i + 1;j < k ;j++) {
            finalyMin = min(finalyMin, distance(sortOfx[temp[i]], sortOfx[temp[j]]));
        }
    }

    return finalyMin;
}

int main() {
    vector<pair<double, double>> point;
    int n;
    cin >> n;
    for (int i = 0;i < n;i++) {
        double x, y;cin >> x >> y;
        point.push_back({ x,y });
    }
    vector<pair<double, double>> sortOfx(point);      //按x轴从小到大排序
    sort(sortOfx.begin(), sortOfx.end(), [](const pair<double, double>& a, const pair<double, double>& b) {
        return a.first < b.first;
        });

    double ans = dfs(sortOfx,n, 0, n - 1);
    printf("%.4f", ans);
}

加上排序只能过4个测试点,复杂度弄高了,所以其实区域内最小值集很少么,不需要筛选

2024/11/21 20:49
加载中...