n<=10000个点,求欧几里德距离最小的一对点。
经典分治,把这些点按x排序,分成两半,每边分别算答案,答案是左边的最小,右边的最小,左右组起来的最小三者的最小。发现只有左右组的有点难写。
假设左右两半各自的最小中的最小是d,左半边最右的点横坐标是X1,右半边最左的点的横坐标是X2。那么只需要坐标在X1-d到X2+d的范围内的点找更小的距离。如下图。
极端地,x1和x2相等时,x1上的某一个点最多可能和多少点组更小的距离呢?
假如左半边上在x1上有一个大大的点,那么右半边的点只有在圆形区域内才可能组成更小距离。而由于右边的点的最小距离不小于d,因此涉及到圆形区域对应的纵坐标范围的点最多有:
这样六个点,也就是说,比如左边那个点纵坐标y,只要在右边找到纵坐标大于等于y的第一个点,然后用它上下的六个点来和左边那个点凑更短的距离即可。这样,只需要把两半横坐标符合的点装进两个数组里,按y排序,两个指针扫一次即可。
1 #include2 #include 3 #include 4 #include 5 #include 6 //#include 7 using namespace std; 8 9 int n;10 #define maxn 1001111 struct Point12 {13 double x,y;14 }p[maxn],a[maxn],b[maxn];int la=0,lb=0;15 bool cmpx(const Point &a,const Point &b) { return a.x >1;27 double ans=min(merge(L,mid),merge(mid+1,R));28 la=lb=0;29 for (int i=L;i<=mid;i++) if (p[mid].x-p[i].x<=ans) a[++la].x=p[i].x,a[la].y=p[i].y;30 for (int i=mid+1;i<=R;i++) if (p[i].x-p[mid+1].x<=ans) b[++lb].x=p[i].x,b[lb].y=p[i].y;31 sort(a+1,a+1+la,cmpy);sort(b+1,b+1+lb,cmpy);32 int j=1;33 for (int i=1;i<=la;i++)34 {35 while (j<=lb && b[j].y