1 #include<cstdio> 2 #include<cmath> 3 #include<queue> 4 #include<cstring> 5 #include<string> 6 #include<algorithm> 7 #define CLR(a,b) memset((a),(b),sizeof((a))) 8 using namespace std; 9  10 typedef long long ll;11 const double inf = 0x3f3f3f3f;12 const int N = 2e5+1;13 int n;14 struct Point{15     int x, y;16 }a[N], midp[N];17 double dis(Point a, Point b){18     return sqrt(1.*(a.x - b.x)*(a.x - b.x) + 1.*(a.y - b.y)*(a.y - b.y));19 }20 bool cmp1(Point a, Point b){21     return a.x < b.x;22 }23 bool cmp2(Point a, Point b){24     return a.y < b.y;25 }26 double solve(int l, int r){27     if(l == r ||l + 1 == r) return inf;28     if(l + 2 == r) return dis(a[l],a[l+1]) + dis(a[l+1],a[r]) + dis(a[l],a[r]);29  30     int m = l + (r-l)/2;31     double d1 = solve(l, m);32     double d2 = solve(m+1, r);33     double d = min(d1, d2);34     double dd = d/2.0;35     double ans = d;36  37     int cnt = 0, i, j, k;38     for(i = l; i <= r; ++i)39         if(fabs(a[m].x - a[i].x) <= dd)40             midp[++cnt] = a[i];41     sort(midp+1, midp+1+cnt, cmp2);42  43     for(i = 1; i < cnt-1; ++i){44         for(j = i+1; j < cnt; ++j){45             if(midp[j].y - midp[i].y > dd)46                 break;47             for(k = j+1; k <= cnt; ++k){48                 if(midp[k].y - midp[i].y > dd)49                     break;50                 double c = dis(midp[i],midp[j])+dis(midp[j],midp[k])+dis(midp[i],midp[k]);51                 ans = min(ans, c);52             }53         }54     }55     return ans;56 }57 int main(){58     scanf("%d", &n);59     for(int i = 1; i <= n; ++i)60         scanf("%d%d", &a[i].x, &a[i].y);61     sort(a+1, a+1+n, cmp1);62     printf("%.6lf\n", solve(1,n));63     return 0;64 }