题面：BJWC2011 最小三角形

$ solution: $

昨天才学完平面最近点对，今天就要求平面最近的三个点，显然不是巧合。

仔细一思考，我们用来求平面最近点对的方法不就可以用到三个点上吗？

就是按x轴排序，然后不断二分，在向上回溯的同时更新我们的ans，比如当前这个区间，距离中点水平距离超过ans/2的点必然不会更新答案！而且通过与最近点对同理的证明，我们在中间那个水平宽为ans的区间内，竖直距离小于ans/2的点绝对很少（至少我们能接受！），所以我们可以看代码了！

$ code: $

#include<iostream>

#include<cstdio>

#include<iomanip>

#include<algorithm>

#include<cstring>

#include<cstdlib>

#include<ctime>

#include<cmath>

#include<vector>

#include<queue>

#include<map>

#include<set>

#define ll long long

#define db double

#define rg register int

using namespace std;

const db inf=1e16;

struct su{

	db x,y;

}a[200005],b[200005];

db xx,yy;

int n;

inline int qr(){

	char ch; int sign=1;

	while((ch=getchar())<'0'||ch>'9')

		if(ch=='-')sign=-1;

	int res=ch^48;

	while((ch=getchar())>='0'&&ch<='9')

		res=res*10+(ch^48);

	return res*sign;

}

inline bool cmp_x(su x,su y){return x.x<y.x;}

inline bool cmp_y(su x,su y){return x.y<y.y;}

inline db dis2(su x,su y){

	xx=(y.x-x.x),yy=(y.y-x.y);

	return sqrt(xx*xx+yy*yy);

}

inline db dis3(su x,su y,su z){

	return dis2(x,y)+dis2(x,z)+dis2(y,z);

}

inline db find(int l,int r){

	if(l+1>=r)return inf;

	int mid=(l+r)>>1;

	db d=min(find(l,mid),find(mid+1,r));

	while(a[l].x+d<a[mid].x)++l;

	while(a[r].x-d>a[mid].x)--r;

	int t=0;

	for(rg i=l;i<=r;++i)b[++t]=a[i];

	sort(b+1,b+t+1,cmp_y);

	for(rg i=1;i<=t;++i)

		for(rg j=i+1;j<=t;++j)

			if(b[j].y-b[i].y>=d)break;

			else for(rg k=j+1;k<=t;++k)

					 if(b[k].y-b[i].y>=d)break;

					 else d=min(d,dis3(b[i],b[j],b[k])/2);

	return d;

}

int main(){

	freopen("math.in","r",stdin);

	freopen("math.out","w",stdout);

	n=qr();

	for(rg i=1;i<=n;++i)

		a[i].x=qr(),a[i].y=qr();

	sort(a+1,a+n+1,cmp_x);

	printf("%.6lf\n",find(1,n)*2);

	return 0;

}