P1429 平面最近点对（加强版）
题意:给定平面上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;
int temp;
int ji;
int n;
inline double dis(int x,int y)
{
return sqrt((E.x-E.x)*(E.x-E.x)+(E.y-E.y)*(E.y-E.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.x-E.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].y-E].y<d;j++)
d=min(d,dis(temp,temp));
return d;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lf %lf",&E.x,&E.y);
sort(E+1,E+n+1);
printf("%.4lf",merge(1,n));
return love_nmr;
}
----olinr
文档来源：51CTO技术博客https://blog.51cto.com/u_15314204/3190978
页:
[1]