题目大意：给出平面上n个点，求最小的由这些点组成的三角形的周长。（N<=200,000）
思路：点按x坐标排序后分治，每次取出与排在中间的点的横坐标相差不超当前答案一半的点，按y坐标排序后再暴力枚举y坐标相差不超过当前答案一半的三个点统计答案，复杂度O(能过)（听说期望nlogn）。
#include<cstdio> #include<cmath> #include<algorithm> using namespace std; inline int read() { int x,f=1;char c; while((c=getchar())<'0'||c>'9')if(c=='-')f=-1; for(x=c-'0';(c=getchar())>='0'&&c<='9';)x=(x<<3)+(x<<1)+c-'0'; return x*f; } #define MN 200000 double ans=1e18; struct P{int x,y;}p[MN+5],t[MN+5]; bool cmpx(P a,P b){return a.x<b.x;} bool cmpy(P a,P b){return a.y<b.y;} double sqr(double x){return x*x;} double len(P a,P b){return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));} void solve(int l,int r) { if(r-l<2)return; int m=l+r>>1,i,j,k,cnt=0; solve(l,m);solve(m+1,r); for(i=l;i<=r;++i)if(fabs(p[i].x-p[m].x)<ans/2)t[++cnt]=p[i]; sort(t+1,t+cnt+1,cmpy); for(i=1;i<=cnt;++i)for(j=i+1;j<=cnt&&t[j].y-t[i].y<ans/2;++j)for(k=j+1;k<=cnt&&t[k].y-t[i].y<ans/2;++k) ans=min(ans,len(t[i],t[j])+len(t[j],t[k])+len(t[k],t[i])); } int main() { int n=read(),i; for(i=1;i<=n;++i)p[i].x=read(),p[i].y=read(); sort(p+1,p+n+1,cmpx); solve(1,n); printf("%.6lf",ans); }