分治法求最近点对，模板题
第二题稍微判断一下即可
总结一下分治法基本写法：
第一部分：边界判断
第二部分：递归函数
第三部分：区间合并
第一题：
#include<stdio.h>#include<math.h>#include<algorithm>using namespace std;const double eps=1e-8;struct Point {double x,y;}p[100005],tmp[100005];int n;double dist(Point a,Point b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}int cmpxy(Point a,Point b){if(a.x!=b.x) return a.x<b.x;return a.y<b.y;}int cmpy(Point a,Point b){return a.y<b.y;}double Closest_Pair(int left,int right){double d=1e20;if(left==right) return d;if(left+1==right) return dist(p[left],p[right]);int mid=(left+right)>>1;double d1=Closest_Pair(left,mid);double d2=Closest_Pair(mid+1,right);d=min(d1,d2);int k=0;for(int i=left;i<=right;i++){if(fabs(p[mid].x-p[i].x)<d+eps) tmp[k++]=p[i];}sort(tmp,tmp+k,cmpy);for(int i=0;i<k;i++){for(int j=i+1;j<k&&tmp[j].y-tmp[i].y<d+eps;j++){d=min(d,dist(tmp[i],tmp[j]));}}第二题：
/* * Author:lj94093 * Created Time: 2015/5/20 星期三 下午 8:06:52 * File Name:Raid.cpp */#include<stdio.h>#include<string.h>#include<vector>#include<list>#include<deque>#include<queue>#include<stack>#include<map>#include<set>#include<bitset>#include<algorithm>#include<math.h>using namespace std;#define out(x) cout<<#x<<": "<<x<<endlconst double eps(1e-8);const int maxn=100100;const long long inf=-1u>>1;typedef long long ll;struct Point{double x,y;int kind;}p[maxn*2],tmp[maxn*2];int t,n;int cmpxy(Point a,Point b){if(a.x!=b.x) return a.x<b.x;return a.y<b.y;}int cmpy(Point a,Point b){return a.y<b.y;}void init() {scanf("%d",&n);for(int i=0;i<n;i++) {scanf("%lf%lf",&p[i].x,&p[i].y);p[i].kind=0;}for(int i=0;i<n;i++) {scanf("%lf%lf",&p[i+n].x,&p[i+n].y);p[i+n].kind=1;}sort(p,p+2*n,cmpxy);}double dist(Point a,Point b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}double work(int left,int right) {double d=inf;if(left==right) return d;if(left+1==right){if(p[left].kind==p[right].kind) return d;else return dist(p[left],p[right]);}int mid=(left+right)>>1;d=min(work(left,mid),work(mid+1,right));int k=0;for(int i=left;i<=right;i++){if(fabs(p[i].x-p[mid].x)<d-eps) tmp[k++]=p[i];}sort(tmp,tmp+k,cmpy);for(int i=0;i<k;i++){for(int j=i+1;j<k && p[j].y-p[i].y<d-eps;j++){if(p[i].kind==p[j].kind) continue;d=min(d,dist(p[i],p[j]));}}return d;}int main() {#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);#endifscanf("%d",&t);while(t–){init();printf("%.3f\n",work(0,2*n-1)+eps);}return 0;}
，只有流过血的手指才能弹出世间的绝唱。
