Coolest solution using beautiful transformations! Highly Educational stuff
IntuitionThis is coolest video illustrating transformations and reductions. Highly educational. <3This problem is actually easier than P3 if you learn the trans
# Intuition
This is coolest video illustrating transformations and reductions. Highly educational. <3 
This problem is actually easier than P3 if you learn the transformation tricks.

https://www.youtube.com/watch?v=VWITokQZjw8&ab_channel=AlgoUniversity

Disclaimer: Not my video, video by Codeforces master & founder of startup AlgoUniversity. Legend stuff.


# Code

My implementation of idea described in video.
```cpp []
typedef long long ll;
class Solution {
public:
    int maxDistance(int side, vector<vector<int>>& points, int k) {
        int n = (int)points.size();
        vector<ll> param(n);
        ll perim = 4LL * side;
        for (int i = 0; i < n; i++) {
            ll x = points[i][0], y = points[i][1];
            if (y == 0) param[i] = x;
            else if (x == side) param[i] = side + y;
            else if (y == side) param[i] = 2LL * side + (side - x);
            else param[i] = 3LL * side + (side - y);
        }
        sort(param.begin(), param.end());
        vector<ll> ext(2 * n);
        for (int i = 0; i < n; i++) {
            ext[i] = param[i];
            ext[i + n] = param[i] + perim;
        }
        auto canPlace = [&](ll d) -> bool {
            for (int i = 0; i < n; i++) {
                int count = 1;
                ll last = ext[i];
                int pos = i;
                while (true) {
                    auto it = std::lower_bound(ext.begin() + pos + 1, ext.begin() + i + n, last + d);
                    if (it == ext.begin() + i + n) break;
                    pos = it - ext.begin();
                    last = *it;
                    count++;
                    if (count == k) {
                        if (ext[i + n] - last >= d) return true;
                        break;
                    }
                }
            }
            return false;
        };
        ll low = 0, high = 2LL * side + 1;
        while (low < high) {
            ll mid = (low + high) >> 1;
            if (canPlace(mid)) low = mid + 1; else high = mid;
        }
        return (int)(low - 1);
    }
};
```
['C++']