给定n个点，求周长最小的三角形的周长。n<=200000
题解:考虑分治，首先按x坐标排序，然后按照分治的思路不断分下去。
1)对于l和r区间内只有最多两个点的情况，显然它已经没救了。
2)然后取出现在暂时比较优的答案ans，用一个limit=ans/2。
3)把这个区间所有点中和中点x坐标差值不超过limit的点全部拿出来，然后按照y坐标排序。
4)然后大暴力，枚举三个点。
复杂度期望是nlogn^2
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} return x*f; } struct P{ int x,y; }s[200005]; int p[200005],n,cnt=0; double ans=2000000000; bool cmp1(P x,P y){return x.x<y.x;} bool cmp2(int x,int y){return s[x].y<s[y].y;} double sqr(int x){return (double)x*x;} double dis(int x,int y){return sqrt(sqr(s[x].x-s[y].x)+sqr(s[y].y-s[x].y));} int abs(int x){return x<0?-x:x;} void solve(int l,int r) { if(l+1>=r)return;if(l+2==r){ans=min(ans,dis(l,r)+dis(l+1,r)+dis(l,r-1));return;} int mid=(l+r)>>1;solve(l,mid);solve(mid+1,r);cnt=0;double lim=ans/2.000000; for(int i=l;i<=r;i++)if(abs(s[i].x-s[mid].x)<=lim)p[++cnt]=i; sort(p+1,p+cnt+1,cmp2); for(int i=1,j=1;i<=cnt;i++) { for(;j<=cnt&&abs(s[p[j]].y-s[p[i]].y)<=lim;++j); for(int k=i+1;k<j;k++) for(int l=i+1;l<k;l++) ans=min(ans,dis(p[i],p[k])+dis(p[k],p[l])+dis(p[i],p[l])); } } int main() { n=read();for(int i=1;i<=n;i++)s[i].x=read(),s[i].y=read(); sort(s+1,s+n+1,cmp1);solve(1,n); printf("%0.6lf",ans); return 0; }