最近对问题


详解见教材《算法分析与设计基础》

板子

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const double inf = 1e20;
const int maxn = 100005;

struct Point{
    double x, y;
}point[maxn];

int n, mpt[maxn], t;
double ex, ey;

//以x为基准排序
bool cmpxy(const Point& a, const Point& b){
    if (a.x != b.x)
        return a.x < b.x;
    return a.y < b.y;
}

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

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

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

// logn层,每层O(n)的处理,时间复杂度O(nlogn)
double Closest_Pair(int left, int right){ 
    double d = inf;
    if (left == right)
        return d;
    if (left + 1 == right)
        return dis(left, right);
    int mid = (left + right) >> 1;
    double d1 = Closest_Pair(left, mid);
    double d2 = Closest_Pair(mid + 1, right);
    d = min(d1, d2);
    int i, j, k = 0;
    //分离出宽度为d的区间
    for (i = left; i <= right; i++){
        if (fabs(point[mid].x - point[i].x) <= d)
            mpt[k++] = i;
    }
    sort(mpt, mpt + k, cmpy);
    //线性扫描
    for (i = 0; i < k; i++){
        for (j = i + 1; j < k && point[mpt[j]].y - point[mpt[i]].y<d; j++){ // 最多6个点,所以时间复杂度为线性的
            double d3 = dis(mpt[i], mpt[j]);
            if (d > d3) 
            {
                d = d3;
                p1 = mpt[i];
                p2 = mpt[j];
            }
        }
    }
    return d;
}

int main(){
    scanf("%d", &t);
    while (t--){
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%lf %lf", &point[i].x, &point[i].y);
        sort(point, point + n, cmpxy);
        printf("%.4lf\n", Closest_Pair(0, n - 1));
        cout << point[p1].x << " " << point[p1].y << endl;
        cout << point[p2].x << " " << point[p2].y << endl;
    }
    return 0;
}

Author: Mrhh
Reprint policy: All articles in this blog are used except for special statements CC BY 4.0 reprint polocy. If reproduced, please indicate source Mrhh !
评论
 Previous
线性复杂度求解n次多项式 -- Horner算法 线性复杂度求解n次多项式 -- Horner算法
算法分析 代码实现#include<iostream> using namespace std; int main(){ int n, x, sum = 0; cin>>n>>x; int a[20];
2020-11-21
Next 
凸包问题 凸包问题
写在前面,以下算法的时间复杂度都为$O(nlogn)$ 快包讲解见教材《算法设计与分析基础》 #include<stdio.h> #include<stdlib.h> int g_result[240][2]; /* *注:
2020-11-20
  TOC