My Solutions
1. Use the binary search with the help from another binary search2. Use the binary search with the help from the k-pointer method3. Use the binary search with t
**1. Use the binary search with the help from another binary search**
```
/**
 * Time Complexity: O(n * k * log(n) * log(side))
 * Space Complexity: O(n)
 * where `n` is the length of the vector `points`
 */
class Solution {
 public:
  int maxDistance(const int side, const vector<vector<int>> &points, const int k) {
    vector<long long> points_in_line;
    for (const vector<int> &point : points) {
      const int x = point.front();
      const int y = point.back();
      if (x == 0) {
        points_in_line.emplace_back(y);
      } else if (y == side) {
        points_in_line.emplace_back(side + x);
      } else if (x == side) {
        points_in_line.emplace_back(3L * side - y);
      } else {
        points_in_line.emplace_back(4L * side - x);
      }
    }
    sort(points_in_line.begin(), points_in_line.end());

    int low = 1;
    int high = side + 1;
    while (low < high) {
      const int mid = low + ((high - low) >> 1);
      if (check(points_in_line, side, k, mid)) {
        low = mid + 1;
      } else {
        high = mid;
      }
    }
    return high - 1;
  }

 private:
  bool check(const vector<long long> &points_in_line, const int side, const int k, const int min_distance) {
    const int n = static_cast<int>(points_in_line.size());
    bool ret = false;
    for (int i = 0; i + k - 1 < n; ++i) {
      int count = 0;
      for (int j = i; j < n && points_in_line[j] <= points_in_line[i] + 4L * side - min_distance && count < k; ) {
        ++count;
        j = static_cast<int>(lower_bound(points_in_line.begin() + j + 1, points_in_line.end(), points_in_line[j] + min_distance) - points_in_line.begin());
      }
      if (count == k) {
        ret = true;
        break;
      }
    }
    return ret;
  }
};
```
**2. Use the binary search with the help from the k-pointer method**
```
/**
 * Time Complexity: O(n * log(n) + log(side) * n * k)
 * Space Complexity: O(n)
 * where `n` is the length of the vector `points`
 */
class Solution {
 public:
  int maxDistance(const int side, const vector<vector<int>> &points, const int k) {
    vector<long long> points_in_line;
    for (const vector<int> &point : points) {
      const int x = point.front();
      const int y = point.back();
      if (x == 0) {
        points_in_line.emplace_back(y);
      } else if (y == side) {
        points_in_line.emplace_back(side + x);
      } else if (x == side) {
        points_in_line.emplace_back(3L * side - y);
      } else {
        points_in_line.emplace_back(4L * side - x);
      }
    }
    sort(points_in_line.begin(), points_in_line.end());

    int low = 1;
    int high = side + 1;
    while (low < high) {
      const int mid = low + ((high - low) >> 1);
      if (check(points_in_line, side, k, mid)) {
        low = mid + 1;
      } else {
        high = mid;
      }
    }
    return high - 1;
  }

 private:
  bool check(const vector<long long> &points_in_line, const int side, const int k, const int min_distance) {
    const int n = static_cast<int>(points_in_line.size());
    int indices[k];
    memset(indices, 0, sizeof(indices));
    bool ret = false;
    for (; indices[0] + k - 1 < n; ++indices[0]) {
      int i = 1;
      for (; i < k; ++i) {
        for (indices[i] = max(indices[i], indices[i - 1] + 1);
             indices[i] + k - i - 1 < n && points_in_line[indices[i]] < points_in_line[indices[i - 1]] + min_distance;
             ++indices[i]) {
        }
        if (indices[i] + k - i - 1 == n) {
          break;
        }
      }
      if (i < k) {
        break;
      }

      if (points_in_line[indices[0]] - (points_in_line[indices[k - 1]] - (4L * side)) >= min_distance) {
        ret = true;
        break;
      }
    }
    return ret;
  }
};
```
**3. Use the binary search with the help from the binary lifting**
```
/**
 * Time Complexity: O(log(side) * n * (log(n) + log(k)))
 * Space Complexity: O(n * log(n))
 * where `n` is the length of the vector `points`
 */
class Solution {
 public:
  int maxDistance(const int side, const vector<vector<int>> &points, const int k) {
    vector<long long> points_in_line;
    for (const vector<int> &point : points) {
      const int x = point.front();
      const int y = point.back();
      if (x == 0) {
        points_in_line.emplace_back(y);
      } else if (y == side) {
        points_in_line.emplace_back(side + x);
      } else if (x == side) {
        points_in_line.emplace_back(3L * side - y);
      } else {
        points_in_line.emplace_back(4L * side - x);
      }
    }
    sort(points_in_line.begin(), points_in_line.end());

    int low = 1;
    int high = side + 1;
    while (low < high) {
      const int mid = low + ((high - low) >> 1);
      if (check(points_in_line, side, k, mid)) {
        low = mid + 1;
      } else {
        high = mid;
      }
    }
    return high - 1;
  }

 private:
  bool check(const vector<long long> &points_in_line, const int side, const int k, const int min_distance) {
    constexpr int invalid_next = -1;
    const int n = static_cast<int>(points_in_line.size());
    const int bits = get_bits(n);
    int nexts[bits][n];
    memset(nexts, 0, sizeof(nexts));
    for (int i = 0, j = i + 1; i < n; ++i) {
      for (; j < n && points_in_line[j] - points_in_line[i] < min_distance; ++j) {
      }
      nexts[0][i] = j == n ? invalid_next : j;
    }

    for (int bit = 1; bit < bits; ++bit) {
      for (int i = 0; i < n; ++i) {
        const int mid_next = nexts[bit - 1][i];
        nexts[bit][i] = mid_next == invalid_next ? invalid_next : nexts[bit - 1][mid_next];
      }
    }

    bool ret = false;
    for (int start = 0; start + k - 1 < n; ++start) {
      int end = start;
      for (int bit = 0, jump = k - 1; jump > 0; ++bit, jump >>= 1) {
        if ((jump & 1) == 1) {
          end = nexts[bit][end];
          if (end == invalid_next) {
            break;
          }
        }
      }
      if (end != invalid_next && points_in_line[start] - (points_in_line[end] - (4L * side)) >= min_distance) {
        ret = true;
        break;
      }
    }
    return ret;
  }

  int get_bits(const int n) {
    int ret = 0;
    for (int num = n; num > 0; num >>= 1) {
      ++ret;
    }
    return ret;
  }
};
```
**4. Use the binary search with the help from the DFS on a graph**
```
/**
 * Time Complexity: O(n * (log(n) + log(side)))
 * Space Complexity: O(n)
 * where `n` is the length of the vector `points`
 */
class Solution {
 public:
  int maxDistance(const int side, const vector<vector<int>> &points, const int k) {
    vector<long long> points_in_line;
    for (const vector<int> &point : points) {
      const int x = point.front();
      const int y = point.back();
      if (x == 0) {
        points_in_line.emplace_back(y);
      } else if (y == side) {
        points_in_line.emplace_back(side + x);
      } else if (x == side) {
        points_in_line.emplace_back(3L * side - y);
      } else {
        points_in_line.emplace_back(4L * side - x);
      }
    }
    sort(points_in_line.begin(), points_in_line.end());

    int low = 1;
    int high = side + 1;
    while (low < high) {
      const int mid = low + ((high - low) >> 1);
      if (check(points_in_line, side, k, mid)) {
        low = mid + 1;
      } else {
        high = mid;
      }
    }
    return high - 1;
  }

 private:
  bool check(const vector<long long> &points_in_line, const int side, const int k, const int min_distance) {
    const int n = static_cast<int>(points_in_line.size());
    vector<int> graph[n + 1];
    for (int i = 0, j = i + 1; i < n; ++i) {
      for (; j < n && points_in_line[j] - points_in_line[i] < min_distance; ++j) {
      }
      graph[j].emplace_back(i);
    }

    bool ret = false;
    vector<int> path({n});
    return dfs(points_in_line, side, k, min_distance, graph, path);
  }

  bool dfs(const vector<long long> &points_in_line,
           const int side,
           const int k,
           const int min_distance,
           const vector<int> *graph,
           vector<int> &path) {
    const int n = static_cast<int>(path.size());
    if (n == k + 1) {
      return points_in_line[path.back()] - (points_in_line[path[n - k]] - (4L * side)) >= min_distance;
    }

    bool ret = false;
    for (const int next_node : graph[path.back()]) {
      path.emplace_back(next_node);
      if (dfs(points_in_line, side, k, min_distance, graph, path)) {
        ret = true;
        break;
      }
      path.pop_back();
    }
    return ret;
  }
};
```
**5. Use the binary search with the help from the DP**
```
/**
 * Time Complexity: O(n * (log(n) + log(side)))
 * Space Complexity: O(n)
 * where `n` is the length of the vector `points`
 */
class Solution {
 public:
  int maxDistance(const int side, const vector<vector<int>> &points, const int k) {
    vector<long long> points_in_line;
    for (const vector<int> &point : points) {
      const int x = point.front();
      const int y = point.back();
      if (x == 0) {
        points_in_line.emplace_back(y);
      } else if (y == side) {
        points_in_line.emplace_back(side + x);
      } else if (x == side) {
        points_in_line.emplace_back(3L * side - y);
      } else {
        points_in_line.emplace_back(4L * side - x);
      }
    }
    sort(points_in_line.begin(), points_in_line.end());

    int low = 1;
    int high = side + 1;
    while (low < high) {
      const int mid = low + ((high - low) >> 1);
      if (check(points_in_line, side, k, mid)) {
        low = mid + 1;
      } else {
        high = mid;
      }
    }
    return high - 1;
  }

 private:
  bool check(const vector<long long> &points_in_line, const int side, const int k, const int min_distance) {
    const int n = static_cast<int>(points_in_line.size());
    /**
     * path[i] stands for the length of the path,
     * which starts from `points_in_line[i]` to the end of `points_in_line`, and
     * the distance of whose any two adjacent nodes is greater than or equal to `min_distance`
     */
    int path[n + 1];
    memset(path, 0, sizeof(path));
    /**
     * end[i] stands for the ending node of the path,
     * which starts from `points_in_line[i]` to the end of `points_in_line`, and
     * the distance of whose any two adjacent nodes is greater than or equal to `min_distance`
     */
    int end[n];
    memset(end, -1, sizeof(end));
    bool ret = false;
    for (int j = n, i = n - 1; i > -1; --i) {
      for (; points_in_line[j - 1] - points_in_line[i] >= min_distance; --j) {
      }
      path[i] = path[j] + 1;
      end[i] = path[i] == 1 ? i : end[j];
      if (path[i] == k && points_in_line[i] - (points_in_line[end[i]] - (4L * side)) >= min_distance) {
        ret = true;
        break;
      }
    }
    return ret;
  }
};
```
['C++']