题意：
给平面上的n个点，求两点间的最短距离。
分析：
分治法，，保存点用vector会tle…
代码：
//poj 3714//sep9#include <iostream>#include <algorithm>#include <cmath>using namespace std;const double INF=1e50;struct P{double x,y;int type;}p[240000],b[240000];bool cmp_x(P a,P b){return a.x<b.x;}bool cmp_y(P a,P b){return a.y<b.y;}double closest_pair(P *a,int n){if(n<=1)return INF;int m=n/2;double x=a[m].x;double d=min(closest_pair(a,m),closest_pair(a+m,n-m));inplace_merge(a,a+m,a+n,cmp_y);int yn=0;for(int i=0;i<n;++i){if(fabs(a[i].x-x)>=d)continue;for(int j=0;j<yn;++j){double dx=a[i].x-b[yn-1-j].x;double dy=a[i].y-b[yn-1-j].y;if(dy>=d)break;if(a[i].type==b[yn-1-j].type)continue;d=min(d,sqrt(dx*dx+dy*dy));}b[yn++]=a[i];}return d;}int main(){int cases;scanf("%d",&cases);while(cases–){int i,n;scanf("%d",&n);for(i=0;i<n;++i){scanf("%lf%lf",&p[i].x,&p[i].y);p[i].type=0;}for(i=n;i<2*n;++i){scanf("%lf%lf",&p[i].x,&p[i].y);p[i].type=1;}n=2*n;sort(p,p+n,cmp_x);printf("%.3f\n",closest_pair(p,n)+1e-6);}return 0;}
别想一下造出大海，必须先由小河川开始。
