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

POOPE

题意:给定平面上n个点，找出其中的一对点的距离，使得在这n个点的所有点对中，该距离为所有点对中最小的
这题
分治O（nlogn）
貌似好久没做分治题了
有点生
而且精度还卡了我半天。。。。QAQ

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define love_nmr 0
struct node
{
  double x,y;
  friend bool operator < (const node &a,const node &b)
  {
    if(a.x<b.x) return true;
    if(a.x>b.x) return false;
    if(a.y<b.y) return true;
    return false;
  }
};
node E[200500];
int temp[200500];
int ji;
int n;
inline double dis(int x,int y)
{
  return sqrt((E[y].x-E[x].x)*(E[y].x-E[x].x)+(E[y].y-E[x].y)*(E[y].y-E[x].y));
}
inline double merge(int left,int right)
{
  if(left==right)
    return (double)0x7fffffff;
  if(left+1==right)
    return dis(left,right);
  int mid=(left+right)>>1;
  double d1=merge(left,mid);
  double d2=merge(mid+1,right);
  double d=min(d1,d2);  
  ji=0;
  for(int i=left;i<=right;i++)
    if(fabs(E[mid].x-E[i].x)<=d)
      temp[++ji]=i;
  sort(temp+1,temp+ji+1);
  for(int i=1;i<=ji;i++)
    for(int j=i+1;j<=ji&&E[temp[j]].y-E[temp[i]].y<d;j++)
      d=min(d,dis(temp[i],temp[j]));
  return d;
}
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+n+1);
  printf("%.4lf",merge(1,n));
  return love_nmr;
}

----olinr