You can see my solution above. Enumerating the answer instead of binary search, you will get a solution of $$$O(n\sqrt{n})$$$ complexity.

I have a strange solution using binary search instead of BFS. Maybe it can help you when you can't think about BFS.

Let us consider the answer is $$$k$$$. The set of points whose distance between $$$(x_i,y_i)$$$ equal $$$k$$$ form a diamond. It's our job to find whether it is "full" with points given in the problem. Diamonds are annoying. We can turn it with $$$45$$$ degree to make it a square. Now we can sort the points in the order $$$x_i+y_i$$$ so every points in the same oblique line, from top left to bottom right, stay together. Then we can calculate the number of consecutive points in the way from bottom left to top right. Using rmq to calculate the smallest one and check whether it is legal, or "full" anyway. Obviously, the answer has monotonicity, so we can use binary search.

The time complexity of this algorithm is also $$$O(n\log{n})$$$.

My solution 149159334

Why I think D is much harder than C and E?

Can anyone give me any suggestions on how to learn dp well?