板子之--分治求最近點對

題目一：HDU-1007

題意：給n個二維座標，求任意兩點最近的歐幾里得距離的一半。

參考部落格：部落格

比較重要的一句：

因為有了這個特性，所以排序後分治合併的過程的時間複雜度 才有了合理性。。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct node
{
    double x,y;
};
bool cmpx(node a,node b)
{
    return a.x<b.x;
}
bool cmpy(node a,node b)
{
    return a.y<b.y;
}
node p[N], a[N];
int cnt, n;
double dis(node a, node b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double run(int l, int r)
{

    if(l + 1 == r) return dis(p[l], p[r]);
    if(l + 2 == r){
        return min({dis(p[l],p[l+1]), dis(p[l],p[l+2]), dis(p[l+1],p[l+2])});
    }
    int mid = l + r >> 1;
    double ans = min(run(l, mid), run(mid+1, r));
    cnt = 0;
    for(int i=l;i<=r;++i){
        if(p[i].x >= p[mid].x - ans && p[i].x <= p[mid].x + ans){
            a[cnt++] = p[i];
        }
    }
    sort(a, a+cnt, cmpy);
    for(int i=0;i<cnt;++i){
        for(int j=i+1;j<cnt;++j){
            if(a[j].y-a[i].y > ans) break;
            ans = min(ans, dis(a[i], a[j]));
        }
    }
    return ans;

}
int main()
{
    while(~scanf("%d", &n)&&n){
        for(int i=0;i<n;++i){
            scanf("%lf%lf", &p[i].x,&p[i].y);
        }
        sort(p, p+n, cmpx);
        printf("%.2f\n", run(0, n - 1) / 2);
    }
}

題目二：最近的兩個點

其實就多了一維，上面的板子不動，多加個z即可。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct node
{
    double x,y,z;
};
bool cmpx(node a,node b)
{
    return a.x<b.x;
}
bool cmpy(node a,node b)
{
    return a.y<b.y;
}
node p[N], a[N];
int cnt, n;
double dis(node a, node b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z));
}
double run(int l, int r)
{

    if(l + 1 == r) return dis(p[l], p[r]);
    if(l + 2 == r){
        return min({dis(p[l],p[l+1]), dis(p[l],p[l+2]), dis(p[l+1],p[l+2])});
    }
    int mid = l + r >> 1;
    double ans = min(run(l, mid), run(mid+1, r));
    cnt = 0;
    for(int i=l;i<=r;++i){
        if(p[i].x >= p[mid].x - ans && p[i].x <= p[mid].x + ans){
            a[cnt++] = p[i];
        }
    }
    sort(a, a+cnt, cmpy);
    for(int i=0;i<cnt;++i){
        for(int j=i+1;j<cnt;++j){
            if(a[j].y-a[i].y > ans) break;
            ans = min(ans, dis(a[i], a[j]));
        }
    }
    return ans;

}
int main()
{
    scanf("%d", &n);
    for(int i=0;i<n;++i){
        scanf("%lf%lf%lf", &p[i].x,&p[i].y,&p[i].z);
    }
    sort(p, p+n, cmpx);
    printf("%.3f\n", run(0, n - 1));
}