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;
  int INFTY = 123456789;
  struct Point {
    int x;
    int y;
  } INF;
  inline bool operator==(const Point& lhs, const Point& rhs) {
    return ((lhs.x == rhs.x) && (lhs.y == rhs.y));
  }
  bool compPoint(const Point& a, const Point& b) {
    if (a.x < b.x) {
      return true;
    }
    if (a.x > b.x) {
      return false;
    }
    return a.y < b.y;
  }
  bool coll(Point p1, Point p2, Point p3) {
    return (((long long int)p1.x * ((long long int)p2.y - (long long int)p3.y) +
             (long long int)p2.x * ((long long int)p3.y - (long long int)p1.y) +
             (long long int)p3.x * ((long long int)p1.y - (long long int)p2.y)) ==
            0);
  }
  long double hyp(Point p1, Point p2) {
    long double dx = 1.0 * (p1.x - p2.x);
    long double dy = 1.0 * (p1.y - p2.y);
    return hypot(dx, dy);
  }
  int binarySearch(Point arr[], int p, int r, Point num) {
    if (p <= r) {
      int mid = (p + r) / 2;
      if (arr[mid] == num)
        return mid;
      else if (compPoint(arr[mid], num))
        return binarySearch(arr, mid + 1, r, num);
      else
        return binarySearch(arr, p, mid - 1, num);
    }
    return -1;
  }
  int main() {
    cout << setprecision(10);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    INF.x = INFTY;
    INF.y = INFTY;
    cin >> n;
    cin >> k;
    k--;
    Point PTL[n];
    for (int i = 0; i < n; i++) {
      int a, b;
      Point p;
      cin >> a;
      cin >> b;
      p.x = a;
      p.y = b;
      PTL[i] = p;
    }
    if (n == 3) {
      if (k == 0) {
        cout << min(hyp(PTL[0], PTL[2]), hyp(PTL[0], PTL[1])) +
                    hyp(PTL[1], PTL[2]);
      }
      if (k == 1) {
        cout << min(hyp(PTL[1], PTL[2]), hyp(PTL[0], PTL[1])) +
                    hyp(PTL[0], PTL[2]);
      }
      if (k == 2) {
        cout << min(hyp(PTL[0], PTL[2]), hyp(PTL[2], PTL[1])) +
                    hyp(PTL[1], PTL[0]);
      }
    } else {
      int impostidx = -1;
      if (coll(PTL[0], PTL[1], PTL[2])) {
        for (int i = 3; i < n; i++) {
          if (!coll(PTL[0], PTL[1], PTL[i])) {
            impostidx = i;
            break;
          }
        }
      } else {
        if (coll(PTL[0], PTL[1], PTL[3])) {
          impostidx = 2;
        }
        if (coll(PTL[0], PTL[2], PTL[3])) {
          impostidx = 1;
        }
        if (coll(PTL[2], PTL[1], PTL[3])) {
          impostidx = 0;
        }
      }
      if (impostidx == -1) {
        cout << "find impost error";
        return 10;
      }
      Point impPt = PTL[impostidx];
      Point chosenPt = PTL[k];
      PTL[impostidx] = INF;
      sort(PTL, PTL + n, compPoint);
      Point first = PTL[0], last = PTL[n - 2];
      long double range = hyp(first, last);
      if (impPt == chosenPt) {
        cout << min(hyp(impPt, first), hyp(impPt, last)) + range;
      } else {
        long double min_v = 1e12;
        for (int i = 0; i < n - 2; i++) {
          min_v = min(min_v, hyp(PTL[i], impPt) + hyp(PTL[i + 1], impPt) -
                                 hyp(PTL[i], PTL[i + 1]));
        }
        if (chosenPt == first) {
          long double cm = min(hyp(impPt, last), min_v);
          for (int i = 0; i < n - 2; i++) {
            cm = min(cm, hyp(PTL[i], impPt) + hyp(last, impPt) -
                             hyp(PTL[i], PTL[i + 1]));
          }
          cout << cm + range;
        } else if (chosenPt == last) {
          long double cm = min(hyp(impPt, first), min_v);
          for (int i = 0; i < n - 2; i++) {
            cm = min(cm, hyp(PTL[i + 1], impPt) + hyp(first, impPt) -
                             hyp(PTL[i], PTL[i + 1]));
          }
          cout << cm + range;
        } else {
          int loc = binarySearch(PTL, 0, n - 2, chosenPt);
          long double curMin =
              min_v + min(hyp(chosenPt, first), hyp(chosenPt, last));
          Point prevPt = PTL[loc - 1];
          Point postPt = PTL[loc + 1];
          curMin = min(curMin, hyp(impPt, first) + hyp(impPt, postPt) -
                                   hyp(chosenPt, postPt));
          curMin = min(curMin, hyp(impPt, last) + hyp(impPt, prevPt) -
                                   hyp(chosenPt, prevPt));
          long double cm = min(hyp(impPt, last), min_v);
          for (int i = 0; i < n - 2; i++) {
            cm = min(cm, hyp(PTL[i], impPt) + hyp(last, impPt) -
                             hyp(PTL[i], PTL[i + 1]));
          }
          cm += hyp(chosenPt, first);
          long double cm2 = min(hyp(impPt, first), min_v);
          for (int i = 0; i < n - 2; i++) {
            cm2 = min(cm2, hyp(PTL[i], impPt) + hyp(first, impPt) -
                               hyp(PTL[i], PTL[i + 1]));
          }
          cm2 += hyp(chosenPt, last);
          if (cm < curMin) {
            curMin = cm;
          }
          if (cm2 < curMin) {
            curMin = cm2;
          }
          cout << curMin + range;
        }
      }
    }
    return 0;
  }
  