【计几】平面欧氏距离最近点对

众所周知，平面欧氏距离最远点对可以用旋转卡壳做，平面欧氏距离最近点对可以用分治做。

---

平面欧氏距离最近点对算法（时间复杂度（分治）： O ( n   l o g n ) O(n~logn) O(n logn)）

• 算法详细思路及时间复杂度证明过程：平面最近点对 - OI Wiki

• 模板来源：平面最近点对 - 神之右大臣

---

【模板题】SPOJ-Closest Point Pair

题意：求平面最近点对的编号。

模板：

#include
#include
#include
#include
using namespace std;

const int N=2e5+10;
typedef long long LL;
const double inf = 1e18;


struct point{
    double x, y;
    int id;
}P[N];

bool cmp_x(point a, point b){
    if(a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}
bool cmp_y(int a, int b){
    return P[a].y < P[b].y;
}

int ansa, ansb; //从哪两个点得到最优解
double ans = inf;
double get_dis(int l, int r){
    double res = sqrt((P[l].x - P[r].x) * (P[l].x - P[r].x) + (P[l].y - P[r].y) * (P[l].y - P[r].y));
    if(res < ans) ans = res, ansa = P[l].id, ansb = P[r].id;
    return res;
}

int tmp[N]; // 存P[]的下标
int pos;

void closest_pair(int l, int r)
{
    if(l == r) return ;
    if(l == r - 1) { get_dis(l, r); return ; }

    int mid = l + r >> 1;
    closest_pair(l, mid);
    closest_pair(mid + 1, r);

    pos = 0;
    for(int i=l; i<=r; i++)
        if(fabs(P[i].x - P[mid].x) < ans) tmp[pos++] = i;
    sort(tmp, tmp + pos, cmp_y);

    for(int i=0; i ansb) swap(ansa, ansb);

    printf("%d %d %.6fn", ansa, ansb, ans);


    system("pause");
    return 0;
}

• 关于 closest_pair() 函数返回类型：可以返回 [ l , r ] [l,r] [l,r] 内的最近点距离，也可以设为void，然后在 get_dis() 函数中更新 a n s ans ans 。

---

【计几】平面最短欧氏距离点对题集