Explained | Clean Code | 73ms
IntuitionTransform the 2D square boundary into a 1D circular array to find the maximum possible minimum Manhattan distance between k selected points using binar
# Intuition
Transform the 2D square boundary into a 1D circular array to find the maximum possible minimum Manhattan distance between k selected points using binary search.

# Approach
1. **Convert to circular 1D problem**: Sort points counter-clockwise around the square perimeter to create a linear ordering.

2. **Binary search for optimal distance**: Search for the maximum possible minimum distance between any two selected points.
   - Use `lower_bound` to find the first distance value that allows selecting k points
   - Search in reverse (from maximum to minimum) using a "reverse distance" parameter
   
3. **Jump array optimization**: For each distance value:
   - Calculate how far to "jump" from each point to find the next valid point
   - Precompute jumps for all points to avoid redundant calculations
   
4. **Dynamic programming**: Build solutions backward to efficiently find sequences of points
   - For each starting position, determine maximum number of points that can be selected
   - Track landing position after following all jumps

5. **Cycle detection optimization**: Check if any sequence forms a cycle that includes k or more points to quickly validate a given distance

# Complexity
- Time complexity: O(n · log(side) + n · log(n))

# Code
```cpp []
#include <ranges>

class Solution {
public:
    int maxDistance(int side, const vector<vector<int>>& in_points, int k) {
        // in_points -> SortPoint; sort counter-clockwise around the square
        auto sorted_points = in_points
            | ::views::transform([side](const auto& p) { return SortPoint(p[0], p[1], side); })
            | ::ranges::to<vector>();
        ::sort(sorted_points.begin(), sorted_points.end());

        // For each point i, jump[i] stores how many positions to skip to reach the first
        // point that has Manhattan distance >= dist from point i
        vector<int> jump(sorted_points.size());
        // For each starting position i:
        // first: maximum number of points we can select with minimum distance >= dist
        // second: the position we land at after following all possible jumps till end and 1 after end
        vector<pair<int, int>> beg_2_len_suff_landing(sorted_points.size());

        // Binary search to find the maximum possible minimum distance
        // Effectively counting down from dist_end-1 to 0 using rev_dist
        // lower_bound finds the first rev_dist where we can fit k points
        int dist_end = side * 2; // Maximum possible Manhattan distance on a square
        return dist_end - *::ranges::lower_bound(
            // Effectively downcount from dist_end-1 to 0
            // lower_bound is the first rev_dist (i.e. max dist) where we can fit k points
            ::views::iota(0, dist_end),
            k,
            [dist_end, &sorted_points, &jump, &beg_2_len_suff_landing](int rev_dist, int k) {
                // Semantics of the comparator-lambda is: fittable_points_count < k
                // i.e. lower_bound is the first rev_dist (i.e. max dist) the lambda returns false
                int dist = dist_end - rev_dist;
                const int N = sorted_points.size();
                // Precompute jumps: for each point, find the first next point that is at least 'dist' away
                for (int i = 0, j = 0; i < N; ++i) {
                    // Loop until we find a point that's far enough (at least 'dist' away)
                    // We consider the circular array by using modulo
                    while (j < i + N && sorted_points[j % N] - sorted_points[i] < dist)
                        ++j;
                    jump[i] = j - i;
                }
                // Dynamic programming to find longest sequences of points with minimum distance >= dist
                // Work backwards to build solutions from smaller subproblems
                for (int i = N - 1; ~i; --i) {
                    int j = i + jump[i];
                    beg_2_len_suff_landing[i] =
                        // If jump lands outside array bounds, we can only take this one point
                        j >= N ? make_pair(1, j % N) :
                        // Otherwise, we can take this point plus whatever we can get starting from j
                        make_pair(beg_2_len_suff_landing[j].first + 1, beg_2_len_suff_landing[j].second);
                    // Optimization: if we find a sequence that wraps around (landing <= i)
                    // and has enough points (>= k), we've found a valid solution for this distance
                    if (beg_2_len_suff_landing[i].second <= i && beg_2_len_suff_landing[i].first >= k)
                        return false; // fittable_points_count >= k
                }
                return true; // fittable_points_count < k
            });
    }

private:
    // Point types based on which side of the square they're on
    static constexpr int kTBtm = 0, kTRgh = 1, kTTop = 2, kTLft = 3;

    struct SortPoint {
        int type, x, y;
        // Classify point based on which edge of the square it lies on
        SortPoint(int x, int y, int side)
                : type(y == 0 ? kTBtm :    // Bottom edge
                       y == side ? kTTop : // Top edge
                       x == 0 ? kTLft :    // Left edge
                       kTRgh)              // Right edge
                , x(x), y(y)
        { }
        bool operator<(const SortPoint& other) const { // Counter-clockwise order
            if (type != other.type) return type < other.type;
            switch (type) {
            case kTBtm: return x < other.x; // Bottom: left to right
            case kTRgh: return y < other.y; // Right: bottom to top
            case kTTop: return x > other.x; // Top: right to left
            case kTLft: return y > other.y; // Left: top to bottom
            }
            return false;
        }
        long long operator-(const SortPoint& other) const { // Manhattan distance
            return ::abs<long long>(x - other.x) + ::abs<long long>(y - other.y);
        }
    };
};

```
['C++']