BZOJ 2458: [BeiJing2011]最小三角形【分治】

题面：

平面上有N个点，Xaviera想找出周长最小的三角形。
为了减小问题的难度，这里的三角形也包括共线的三点。
N<=200000

题目分析：

类似于平面最近点对。




三角形是类似的。

（以上摘自Quack大爷的PPT）

Code：

#include<cstdio>
#include<cctype>
#include<cmath>
#include<algorithm>
#define maxn 200005
using namespace std;
template<class T>inline void read(T &a){
	char c;bool f=0;while(!isdigit(c=getchar())) if(c=='-') f=1;
	for(a=c-'0';isdigit(c=getchar());a=a*10+c-'0'); if(f) a=-a;
}
const double eps = 1e-8, inf = 1e20;
struct Point{
	double x,y;
}a[maxn],p[maxn];
inline bool cmpx(const Point &a,const Point &b){return a.x<b.x;}
inline bool cmpy(const Point &a,const Point &b){return a.y<b.y;}
int n;
#define sqr(x) (x)*(x)
inline double dist(const Point &a,const Point &b){return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}
double solve(int l,int r){
	if(r-l<=1) return inf;
	if(l+2==r) return dist(a[l],a[l+1])+dist(a[l],a[r])+dist(a[l+1],a[r]);
	int mid=(l+r)>>1,cnt=0;
	double D=min(solve(l,mid),solve(mid+1,r));
	for(int i=l;i<=r;i++) if(fabs(a[i].x-a[mid].x)<=D*0.5) p[++cnt]=a[i];
	sort(p+1,p+1+cnt,cmpy);
	for(int i=1;i<=cnt;i++)
		for(int j=i+1;j<=cnt;j++){
			if(p[j].y-p[i].y>D*0.5) break;
			for(int k=j+1;k<=cnt;k++)
				if(p[k].y-p[i].y>D*0.5) break;
				else D=min(D,dist(p[i],p[j])+dist(p[j],p[k])+dist(p[i],p[k]));
		}
	return D;
}
int main()
{
	read(n);
	for(int i=1;i<=n;i++) read(a[i].x),read(a[i].y);
	sort(a+1,a+1+n,cmpx);
	printf("%.6f",solve(1,n));
}