C++ | BS + Greedy
Code

# Code
```cpp []
class Solution {
public:
    #define ll long long
    ll dist(vector<int>&a, vector<int> &b)
    {
        return abs((ll)a[0]-b[0])+abs((ll)a[1]-b[1]);
    }
    int nearest(int s,ll d, vector<vector<int>>& p)
    {
        int res=-1,l=s+1,h=p.size()-1;
        while(l<=h)
        {
            int mid=(l+h)/2;
            if(dist(p[mid], p[s])>=d)
            {
                res=mid;
                h=mid-1;
            }
            else
                l=mid+1;
        }
        if(res!=-1)
           return res;
        l=0,h=s-1;
        while(l<=h)
        {
            int mid=(l+h)/2;
            if(dist(p[mid], p[s])>=d)
            {
                res=mid;
                h=mid-1;
            }
            else
                l=mid+1;
        }
        return res;
    }
    bool possible(ll dis,int k,int l,vector<vector<int>>& p)
    {
        int n=p.size();
        for(int i=0;i<n;i++)
        {
            int count=1,s=i;
            while(count<k)
            {
                int next=nearest(s,dis,p);
                if(next!=-1 && dist(p[i],p[next])>=dis)
                {
                    s=next;
                    count++;
                }
                else
                   break;   
            }
            if(count==k)
               return true;   
        }
        return false;
    }
    int maxDistance(int side, vector<vector<int>>& p, int k) 
    {
        ll l=0,h=2*side,res=0;
        // reorder p clockwise
        unordered_map<int,vector<int>>x,y;
        for(auto &v:p)
        {
            if(v[0]==0 && v[1]<side)
               x[0].push_back(v[1]);
            else if(v[1]==side && v[0]<side)
               y[side].push_back(v[0]);
            else if(v[0]==side && v[1]>0)
               x[side].push_back(v[1]);
            else
               y[0].push_back(v[0]);         
        }
        sort(x[0].begin(),x[0].end());
        sort(y[side].begin(),y[side].end());
        sort(y[0].rbegin(),y[0].rend());
        sort(x[side].rbegin(),x[side].rend());
        p.clear();
        for(auto e:x[0])
           p.push_back({0,e});
        for(auto e:y[side])
           p.push_back({e,side});
        for(auto e:x[side])
           p.push_back({side,e});
        for(auto e:y[0])
           p.push_back({e,0});
        while(l<=h)
        {
            ll mid=(l+h)/2;
            if(possible(mid,k,side,p))
            {
                res=mid;
                l=mid+1;
            }
            else
               h=mid-1;
        }
        return res;
    }
};
```
['C++']