hdu1007最近点对（分治）

这道题《算法导论》和《编程之美》都有详细的讲解

分治思想&＃xff1a;先把n个点按x坐标排序&＃xff0c;然后求左边n/2个和右边n/2个的最近距离&＃xff0c;最后合并。

合并要考虑 最近点对 的其中一个点在左边&＃xff0c;另一个在右边的情况。

      如上图&＃xff0c;只需考虑[x-minDist,x&＃43;minDist]的这段区域minDist*&＃xff08;2*minDist&＃xff09;的矩形区域&＃xff0c;这样一个区域最多只有八个点&＃xff08;反推&＃xff09;&＃xff0c;所以只用搜索按坐标y排序后紧随其后的7个点即可。0和1,2,3,4....;1和2,3,4...

     这里有详细的证明点击打开链接

     总的算法复杂度为O&＃xff08;nlogn&＃xff09;

     hdu上面这道题用cin读取数据TLE了&＃xff0c;改为scanf就AC了

#include
#include
#include
#include
#include
using namespace std;const int maxn&＃61;100005;
struct Point{
public:double x,y;
};
Point v[maxn];
int ind[maxn];
bool cmpx(const Point &p1,const Point &p2){return p1.x}bool cmpy(int i1,int i2){return v[i1].y}double dis(const Point& p1, const Point& p2){return sqrt((p2.x-p1.x)*(p2.x-p1.x)&＃43;(p2.y-p1.y)*(p2.y-p1.y));
}
double min(double a,double b)
{return a}
double devide(int l,int r)
{if(r&＃61;&＃61;1&＃43;l)return dis(v[r],v[l]);if(r&＃61;&＃61;2&＃43;l)return min(min(dis(v[l],v[l&＃43;1]),dis(v[l&＃43;1],v[r])),dis(v[l],v[r]));int mid&＃61;(l&＃43;r)/2;int c&＃61;0;double minDis&＃61;min(devide(l,mid),devide(mid&＃43;1,r));for(int i&＃61;l;i<&＃61;r;&＃43;&＃43;i){if(v[i].x<&＃61;v[mid].x&＃43;minDis&&v[i].x>&＃61;v[mid].x-minDis){ind[c&＃43;&＃43;]&＃61;i;}}sort(ind,ind&＃43;c,cmpy);for(int i&＃61;0;i&＃61;minDis)break;minDis&＃61;min(minDis,dis(v[ind[i]],v[ind[j]]));}}return minDis;
}int main()
{//freopen("in.txt","r",stdin);int n;while(cin>>n&&n){double x,y;for(int i&＃61;0;i}