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

· · 题解

题目传送门

题目描述：

给定平面上n个点，找出其中的一对点的距离，使得在这n个点的所有点对中，该距离为所有点对中最小的。

Solution

这题考虑分治。 先将点对按照横坐标排序，每次进行分治时每次以中间的横坐标的点为分界线分治。

对于前两种，好处理，不断地递归分治即可 问题主要处理第三种。 因为我们先进行了递归分治，这是得出了min(1,2)的答案是ans（指的是第1、2种方案的较小值） 这是我们就可以根据ans来限定搜查的范围 很显然，对于一个有效的搜查范围，当且仅当x[i] - x[mid] <=ans，这是一个很显然的结论，当两横坐标之差>ans时，这是绝对不会为最优解的

将这几个点暴力遍历一遍即可。 //还有。。这个实数的坐标是一个坑。。。确实是第一次遇到

Code

#include<bits/stdc++.h>
using namespace std;
int n,maxx=0;
//vector < int , int > xn[200010];
struct node{
    double x,y,num;
}a[200010];

inline bool mycmp(node x,node y){
    return x.x <y.x;
}

inline bool mycmpp(node x,node y){
   return x.y<y.y;
}

double js(node x,node y){
     X=x.x,Y=x.y,XX=y.x,YY=y.y;
    return sqrt((X-XX)*(X-XX) + (Y-YY)*(Y-YY) * 1.0);
}

double dfs(int l,int r){
    double ans=1e12;
    if (l >= r) return 1000000000.00;
    if (l + 1 == r) return js(a[l],a[r]);
    int mid=l+r>>1;
    ans = min(dfs(l,mid) , dfs(mid+1,r));
    int len=0;
    node b[n+10];
    for (int i=l;i<=r;i++)
      if (fabs(a[i].x - a[mid].x) <= ans) b[++len] = a[i]; 
    sort(b+1,b+len+1,mycmpp);
    for (int i=1;i<=len;i++)
      for (int j=i+1;j<=len;j++){
          if (fabs(b[i].y - b[j].y) > ans) break;
          ans = min(ans,js(b[i],b[j]));
      }
    return ans;
}

int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
      scanf("%lf %lf",&a[i].x,&a[i].y);
    sort(a+1,a+n+1,mycmp);
//    dfs(1,n);
    printf("%.4lf",dfs(1,n));
    return 0;
}