C++ | Binary Search
Didn't notice k <= 25 at first glance, otherwise it's pretty straightforward.Code
Didn't notice k <= 25 at first glance, otherwise it's pretty straightforward.

# Code
```cpp []
class Solution {
public:
    int maxDistance(int side, vector<vector<int>>& points, int k) {
        int n = points.size();
        function<int(const vector<int>&)> ix = [&](const vector<int>& p) {
            if (p[0] == 0) return 0;
            else if (p[1] == side) return 1;
            else if (p[0] == side) return 2;
            return 3;
        };
        sort(points.begin(), points.end(), [&](const auto& a, const auto& b) {
            int idxa = ix(a), idxb = ix(b);
            if (idxa != idxb) return idxa < idxb;
            if (a[0] == b[0]) {
                return a[0] == 0 ? a[1] < b[1] : a[1] > b[1];
            }
            if (a[1] == b[1]) {
                return a[1] > 0 ? a[0] < b[0] : a[0] > b[0];
            }
            return true;
        });

        function<int(int, int)> manh = [&](int a, int b) {
            return abs(points[a][0] - points[b][0]) + abs(points[a][1] - points[b][1]);
        };

        vector<long long> dist(n);
        for (int i = 1; i < n; i++) dist[i] = dist[i-1] + manh(i, i - 1);
        int l = 0, r = side + 1;
        int ans = 1;
        while (l < r) {
            int m = (l + r) >> 1;
            bool valid = false;
            for (int start = 0; start < n; start++) {
                int last = start;
                bool ok = true;
                for (int t = 1; t < k; t++) {
                    int idx = lower_bound(dist.begin(), dist.end(), dist[last] + m) - dist.begin();
                    if (idx < n) {
                        last = idx;
                    } else {
                        ok = false;
                        break;
                    }
                }
                if (ok && manh(start, last) >= m) {
                    valid = true;
                    break;
                } 
            }
            if (valid) {
                l = m + 1;
                ans = m;
            } else {
                r = m;
            }
        }
        return ans;
    }
};
```
['C++']