description: You are given N points on an infinite plane with the Cartesian coordinate system on it. N-1 points lay on one line, and one point isn't on that line. You are on point K at the start, and the goal is to visit every point. You can move between any two points in a straight line, and you can revisit points. What is the minimum length of the path? 
  
  Input
  
  The first line contains two integers: N (3 ≤ N ≤ 2*10^5) - the number of points, and K (1 ≤ K ≤ N) - the index of the starting point.
  
  Each of the next N lines contain two integers, A_i, B_i (-10^6 ≤ A_i, B_i ≤ 10^6) - coordinates of the i-th point.
  
  Output
  
  The output contains one number - the shortest path to visit all given points starting from point K. The absolute difference between your solution and the main solution shouldn't exceed 10^-6;
  
  Example
  
  Input
  
  
  5 2
  0 0
  -1 1
  2 -2
  0 1
  -2 2
  
  
  Output
  
  
  7.478709
  
  Note
  
  The shortest path consists of these moves: 
  
  2 -> 5 
  
  5 -> 4 
  
  4 -> 1 
  
  1 -> 3 
  
  There isn't any shorter path possible.
solution: #include <bits/stdc++.h>
  using namespace std;
  inline long long read() {
    long long res = 0, flag = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
      if (c == '-') flag = -1;
      c = getchar();
    }
    while (c >= '0' && c <= '9') res = res * 10 + c - '0', c = getchar();
    return res * flag;
  }
  void print(pair<long long, long long> A) {
    cerr << A.first << ' ' << A.second << "XXX\n";
  }
  const long long N = 2e5 + 20;
  long long D(pair<long long, long long> A, pair<long long, long long> B) {
    return (A.first - B.first) * (A.first - B.first) +
           (A.second - B.second) * (A.second - B.second);
  }
  long double sqr(long double A) { return sqrt(A); }
  const long double eps = 1e-8;
  long long cmp(long double a, long double b) {
    if (fabs(a - b) <= eps) return 0;
    return a < b ? -1 : 1;
  }
  pair<long long, long long> a[N], te;
  long long n, s;
  long long D(long long A, long long B) { return D(a[A], a[B]); }
  mt19937 rnd(time(0));
  bool isl(long long ie[3]) {
    long double d[3];
    long long ct = -1;
    for (long long i = (0), stOxrj = (2); i <= stOxrj; ++i)
      for (long long j = (i + 1), stOxrj = (2); j <= stOxrj; ++j)
        d[++ct] = sqr(D(a[ie[i]], a[ie[j]]));
    sort(d, d + 3);
    return !cmp(d[0] + d[1], d[2]);
  }
  long long nd[10][10], isg[N];
  vector<long long> guan;
  signed main() {
    n = read();
    s = read();
    for (long long i = (1), stOxrj = (n); i <= stOxrj; ++i)
      a[i].first = read(), a[i].second = read();
    te = a[s];
    sort(a + 1, a + n + 1);
    n = unique(a + 1, a + n + 1) - a - 1;
    if (n <= 2) {
      printf("%.10Lf\n", sqr(D(a[1], a[n])));
      return 0;
    }
    if (n <= 3) {
      for (long long i = (1), stOxrj = (n); i <= stOxrj; ++i)
        if (te == a[i]) s = i;
      long double ans = 1e18;
      for (long long i = (1), stOxrj = (n); i <= stOxrj; ++i)
        if (i != s) ans = min(ans, sqr(D(a[i], a[s])));
      for (long long i = (1), stOxrj = (n); i <= stOxrj; ++i)
        for (long long j = (i + 1), stOxrj = (n); j <= stOxrj; ++j)
          if (i != s && j != s) ans += sqr(D(a[i], a[j]));
      printf("%.10Lf\n", ans);
      return 0;
    }
    long long ie[3];
    while (1) {
      for (long long i = (0), stOxrj = (2); i <= stOxrj; ++i)
        ie[i] = rnd() % n + 1;
      long long flg = 0;
      for (long long i = (0), stOxrj = (2); i <= stOxrj; ++i)
        for (long long j = (i + 1), stOxrj = (2); j <= stOxrj; ++j)
          if (ie[i] == ie[j]) flg = 1;
      if (flg) continue;
      if (isl(ie)) break;
    }
    for (long long i = (1), stOxrj = (n); i <= stOxrj; ++i) {
      ie[2] = i;
      if (!isl(ie)) {
        swap(a[i], a[n]);
        break;
      }
    }
    sort(a + 1, a + n);
    for (long long i = (1), stOxrj = (n); i <= stOxrj; ++i)
      if (te == a[i]) s = i;
    isg[s] = isg[1] = isg[n - 1] = isg[n] = 1;
    long long whe = 0, qwq = 1e18;
    for (long long i = (1), stOxrj = (n - 1); i <= stOxrj; ++i)
      if (qwq > D(i, n)) qwq = D(i, n), whe = i;
    isg[whe] = isg[whe - 1] = isg[whe + 1] = 1;
    isg[s] = isg[s - 1] = isg[s + 1] = 1;
    for (long long i = (1), stOxrj = (n); i <= stOxrj; ++i)
      if (isg[i]) guan.push_back(i);
    long double ans = sqr(qwq) * 2;
    ans += sqr(D(1, n - 1)) + min(sqr(D(1, s)), sqr(D(s, n - 1)));
    long long sz = guan.size(), p[15];
    for (long long i = (0), stOxrj = (sz - 1); i <= stOxrj; ++i) p[i] = i;
    do {
      if (guan[p[0]] != s) continue;
      long double nans = 0;
      bool vs[15];
      memset(vs, 0, sizeof(vs));
      for (long long i = (1), stOxrj = (sz - 1); i <= stOxrj; ++i) {
        nans += sqr(D(guan[p[i - 1]], guan[p[i]]));
        long long mn = min(p[i - 1], p[i]);
        long long mx = max(p[i - 1], p[i]);
        if (mx == sz - 1) continue;
        for (long long i = (mn), stOxrj = (mx - 1); i <= stOxrj; ++i) vs[i] = 1;
      }
      bool ok = 1;
      for (long long i = (0), stOxrj = (sz - 3); i <= stOxrj; ++i)
        if (guan[i + 1] - guan[i] != 1 && !vs[i]) ok = 0;
      if (ok) ans = min(ans, nans);
    } while (next_permutation(p, p + sz));
    printf("%.10Lf\n", ans);
    return 0;
  }
  