Monotonic queue with binary search. ;)
IntuitionApproachComplexity
Time complexity:

Space complexity:
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

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

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

# Code
```cpp []
class Solution {
public:
    int maxDistance(int side, vector<vector<int>>& poits, int k) {
        vector<vector<int>> clockwise;
        vector<vector<int>> roxy;

        set<vector<int>> points;
        for(auto it: poits) {
            points.insert(it);

        }

        for(auto it: points) {
            if(it[0] == 0) {
                roxy.push_back(it);
            }
        }
        
        sort(roxy.begin(), roxy.end());
        for(auto it: roxy) {
            points.erase(it);
            clockwise.push_back(it);
        }
        roxy = {};

        for(auto it: points) {
            if(it[1] == side) {
                roxy.push_back(it);
            }
        }

        sort(roxy.begin(), roxy.end());
        for(auto it: roxy) {
            points.erase(it);
            clockwise.push_back(it);
        }

        roxy = {};

        for(auto it: points) {
            if(it[0] == side) {
                roxy.push_back(it);
            }
        }

        sort(roxy.begin(), roxy.end());
        reverse(roxy.begin(), roxy.end());
        for(auto it: roxy) {
            points.erase(it);
            clockwise.push_back(it);
        }

        roxy = {};

        for(auto it: points) {
            if(it[1] == 0) {
                roxy.push_back(it);
            }
        }

        sort(roxy.begin(), roxy.end());
        reverse(roxy.begin(), roxy.end());
        for(auto it: roxy) {
            points.erase(it);
            clockwise.push_back(it);
        }


        long long start = 0, end = 2e9;

        long long ans = 0;

        // for(auto it: clockwise) {
        //     cout << it[0] << " " << it[1] << endl;
        // }
        


        while(start <= end) {
            long long mid = (start + end) / 2;
            

            int points = 0;



            queue<int> stk;
            vector<int> next_bigger(clockwise.size(), -1);

            
            for(int i = 0; i < clockwise.size(); i ++) {
                while(!stk.empty()) {
                    int ind = stk.front();
                    
                    long long dist = abs(clockwise[ind][0] - clockwise[i][0]) + abs(clockwise[ind][1] - clockwise[i][1]);

                    // if(mid == 4) {
                    //     // cout << ind << " hello baby " << i << " " << dist << endl;
                    // }

                    
                    if(dist >= mid) {
                        next_bigger[stk.front()] = i;
                        stk.pop();
                    } else {
                        break;
                    }
                }

                stk.push(i);
            }


            // for(int i = 0; i < clockwise.size(); i ++) {
            //     if(mid == 4) {

            //         cout << clockwise[i][0] << " " << clockwise[i][1] << " " << next_bigger[i] << endl;
            //     }
            // }

            for(int j = 0; j < clockwise.size(); j ++) {
                // lets see if we start from this point.
                

                long long currentx = INT_MIN, currenty = INT_MIN;
                int i = j;
                points = 1;

                while(i != -1 && i < clockwise.size() && points < k) {
                    i = next_bigger[i];
                    if(i == -1) break;

                    long long dist1 = abs(clockwise[j][0] - clockwise[i][0]) + abs(clockwise[j][1] - clockwise[i][1]);

                    if(dist1 < mid) break;
                    points ++;
                }


                if(points >= k) break;
            }

            

            if(points >= k) {
                start = mid + 1;
                ans = max(ans, mid);
            } else {
                end = mid - 1;
            }
        }

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