分治法吧，我也是第一次做题。就以我的理解对hdu1007来讲一下到目前为止我对分治法的理解吧。
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1007
题意：题意很清楚，就是求一个平面内的最近点对，然后输出最近点对距离的一半。
思路：首先能想到的肯定是直接暴力。但是我们看这个数据10e5,直接暴力的话铁定超时，所以就不得不用分治了。。
所谓分治就是先把对应点的x坐标排序，然后再分别求出两部分的最小的距离d1和d2,d=min(d1,d2),当然，当我们把x分为两部分时，然后再递归二分吧，每次到还剩两个数据时直接求出他们的距离。每次返回都和d取最小值。当然这样我们还没有计算不同区间的距离，这个比较重要，我们每次都把各个数据的x和d比较，>的话就肯定不行的了，然后记录<=的数据，另设数组保存。再判断y与d的关系，>的话，肯定也是不行的了。其实我的理解分治就是优化时间复杂度的吧，要是能暴力该有多好。
ac代码：
#include<iostream> #include<algorithm> #include<math.h> #define INF 0x3f3f3f3f #define maxn 100010 using namespace std; struct note { double x,y; }; note p[maxn],t[maxn]; int cmpxy(note a,note b) { if(a.x==b.x) return a.y<b.y; return a.x<b.x; } int cmpy(note a,note b) { return a.y<b.y; } double dis(note a,note b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));//计算两点间的距离 } double closet(int left,int right) { double d=INF;//赋初值为极大 if(left==right) return d;//一个点时，直接返回极大 if(left+1==right)//当分到只剩两个点时直接算出他们的距离 { return dis(p[left],p[right]); } int mid=(left+right)/2;//算中间值 double d1=closet(left,mid); double d2=closet(mid+1,right);//递归 d=min(d1,d2);//更新小值 int k=0; for(int i=left;i<=right;i++) { if(fabs(p[i].x-p[mid].x)<=d)//大于d的就不要了 t[k++]=p[i]; } sort(t,t+k,cmpy);//以y的值由小到大排序 for(int i=0;i<k;i++) { for(int j=i+1;j<k&&t[j].y-t[i].y<d;j++)//大于d就不要了 { d=min(d,dis(t[i],t[j]));//更新d的值，直到找到最小 } } return d; } int main() { int n; while(scanf("%d",&n)!=EOF&&n) { for(int i=0;i<n;i++) { scanf("%lf%lf",&p[i].x,&p[i].y); } sort(p,p+n,cmpxy);//排序，以x的坐标由小到大排序 printf("%.2lf\n",closet(0,n-1)/2);//输出最小的值的一半 } return 0; }
你窥探过我最不安的手，在青春最寒冷的时候。
原文：https://www.cnblogs.com/2000liuwei/p/10638587.html