题意：给出$N$个点，求其中周长最小的三角形（共线的也计算在内）。$N \leq 2 \times 10^5$
这道题唤起了我对平面最近点对的依稀记忆
考虑平面最近点对的分治，将分界线两边的求解改为求三角形的最小边长即可。
小心坐标乘积爆int
不难但就是想不出
1 //This code is written by Itst 2 #include3 #define int long long 4 #define ld long double 5 #define eps (ld)1e-10 6 using namespace std; 7 8 inline int read(){ 9 int a = 0;10 bool f = 0;11 char c = getchar();12 while(c != EOF && !isdigit(c)){13 if(c == '-')14 f = 1;15 c = getchar();16 }17 while(c != EOF && isdigit(c)){18 a = (a << 3) + (a << 1) + (c ^ '0');19 c = getchar();20 }21 return f ? -a : a;22 }23 24 const int MAXN = 200010;25 struct node{26 int x , y;27 }now[MAXN] , pot[MAXN];28 int N;29 30 ld dis(node a , node b){31 return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));32 }33 34 ld len(node a , node b , node c){35 return dis(a , b) + dis(b , c) + dis(a , c);36 }37 38 bool cmp1(node a , node b){39 return a.y < b.y;40 }41 42 ld solve(int l , int r){43 if(r - l <= 4){44 ld minN = 0x3f3f3f3f;45 for(int i = l ; i <= r ; i++)46 for(int j = i + 1 ; j <= r ; j++)47 for(int k = j + 1 ; k <= r ; k++)48 minN = min(minN , len(now[i] , now[j] , now[k]));49 return minN;50 }51 int mid = l + r >> 1;52 ld k = (now[mid].x + now[mid + 1].x) * (ld)0.5 , d1 = solve(l , mid) , d2 = solve(mid + 1 , r) , d = min(d1 , d2);53 sort(now + l , now + r + 1 , cmp1);54 int p = 0;55 for(int i = l ; i <= r ; i++)56 if(fabs(now[i].x - k) + eps < d)57 pot[++p] = now[i];58 for(int i = 1 ; i <= p ; i++)59 for(int j = i + 1 ; j <= p && pot[j].y - pot[i].y + eps < d ; j++)60 for(int k = j + 1 ; k <= p && pot[k].y - pot[i].y + eps < d ; k++)61 d = min(d , len(pot[i] , pot[j] , pot[k]));62 return d;63 }64 65 bool cmp(node a , node b){66 return a.x < b.x;67 }68 69 signed main(){70 #ifdef LG71 freopen("4423.in" , "r" , stdin);72 //freopen("4423.out" , "w" , stdout);73 #endif74 N = read();75 for(int i = 1 ; i <= N ; i++){76 now[i].x = read();77 now[i].y = read();78 }79 sort(now + 1 , now + N + 1 , cmp);80 cout << fixed << setprecision(6) << solve(1 , N);81 return 0;82 }