题解 P1429 平面最近点对（加强版）

Treaker · 2019-08-30 17:09:21 · 题解

解法：

这道题我们可以用分治，把横坐标排序，对于每段区间，我们考虑跨过分界线的贡献(分界线可以用平均值来得到)，我们只需要找距分界线距离在ans以内的点，再分组求距离更新ans即可。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define N (200020)
using namespace std;
int n;
double ans = 2147483647.0;
struct node
{
    double x , y;
    friend bool operator < (const node &a,const node &b)
    {
        if(a.x == b.x)  return a.y < b.y;
        return a.x < b.x;
    }
}e[N] , tmp[N] , temp[N];
void feez(int l,int r)
{
    if(l == r)  return ;
    int mid = (l + r) >> 1 , p = 0 , q = 0;
    feez(l,mid); feez(mid+1,r);
    double fj = (e[mid].x + e[mid+1].x) / 2.0;
    for(int i = l;i <= mid;i ++)    if(fj - e[i].x <= ans) tmp[++ p] = e[i];
    for(int i = mid + 1;i <= r;i ++)    if(e[i].x - fj <= ans)  temp[++ q] = e[i];
    for(int i = 1;i <= p;i ++)  for(int j = 1;j <= q;j ++)
        ans = min(ans,sqrt((tmp[i].x - temp[j].x) * (tmp[i].x - temp[j].x) + (tmp[i].y - temp[j].y) * (tmp[i].y - temp[j].y)));
}
int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++)  scanf("%lf%lf",&e[i].x,&e[i].y);
    sort(e+1,e+1+n);
    feez(1,n);
    printf("%.4f\n",ans);
    return 0;
}