Greedy + Binary Search ||  Clean and Simple to Understand Code || C++
IntuitionWhenever we have to minimize or maximize the values, we can think of binary search for optimal solutions because it helps us to discard one portion and
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Whenever we have to minimize or maximize the values, we can think of binary search for optimal solutions because it helps us to discard one portion and search in other portion.

# Approach
<!-- Describe your approach to solving the problem. -->
1. Convert the 2D square points to 1D plane using simple mathematics.
2. Sort the 1D plane points so that we can leverage lower bound in order to find the Manhattan Distance between two points.
3. Now start applying binary search on the [0, 2 * side].
4. Post that, make a circular array because actually we have given a square so suppose if there are 4 points a, b, c and d, k = 4, so the distance between two consecutive points must be same so..
a = b, b = c, c = d, d = a, hence we need to transform it into a circular array.
5. At last, greedily pick all the k points having the same distance between two consecutive points.
6. If the count equals to k && d = a i.e. you have set of k points of distance d so return true otherwise return false in the check function.

# Complexity
- Time complexity: O(N * logN + N * K + logN)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: O(2N)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
using ll = long long;

class Solution {
public:
    ll map(int side, int x, int y) {
        if (y == 0) return x;
        if (x == side) return side + y;
        if (y == side) return 3LL * side - x;
        return 4LL * side - y;
    }

    bool check(vector<ll> &t, int k, int side, int d) {
        int n = t.size();
        ll L = 4LL * side;
        vector<ll> circular(2 * n);

        for (int i = 0; i < n; i++) {
            circular[i] = t[i];
            circular[i + n] = t[i] + L;
        }

        for (int i = 0; i < n; i++) {
            int count = 1, idx = i;
            ll pos = circular[i]; 
            for (int cnt = 1; cnt < k; cnt++) {
                ll target = pos + d;
                auto it = lower_bound(circular.begin() + idx + 1, 
                circular.begin() + i + n, target);
                if (it == circular.begin() + i + n) {
                    count = -1; // not enough points available from this start
                    break;
                }
                idx = it - circular.begin();
                pos = circular[idx];
                count++;
            }
            if (count == k && (circular[i] + L - pos) >= d) return true;
        }
        return false;
    }

    int maxDistance(int side, vector<vector<int>> &points, int k) {
        int n = points.size();
        int low = 0, high = 2 * side;
        vector<ll> t(n);

        for (int i = 0; i < n; i++) {
            int x = points[i][0], y = points[i][1];
            t[i] = map(side, x, y);
        }
        sort(t.begin(), t.end());

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (check(t, k, side, mid)) {
                low = mid + 1;
            }
            else high = mid - 1;
        }

        return high;
    }
};
```
['C++']