PROBLEM LINK  Author and Editoriallist  AmirReza PoorAkhavan DIFFICULTY – PREREQUISITES – Binarysearch. EXPLANATION – Let's use binarysearch, now the problem is how to check if it’s possible for some fixed D to start at some special point and visit each of the other special points, directly or through other special points. Let’s build a graph and for each pair of vertices put an edge between them if and only if $x_i  x_j + y_i  y_j \geq D$. Now, Check if it’s connected. For the first subtask, it’s really easy, just build the graph naively and check if it’s connected. Let’s check which points are connected to point $(X, Y)$. You can see that $(P, Q)$ is connected to $(X, Y)$ if at least one of the below conditions satisfied:
Let's define two sets of points, one is $F$ which is sorted by $x + y$ of points and $S$ which is sorted by $x  y$ of points. Now consider we are at point $(X, Y)$, we can find the points connected to this point at the beginning or at the end of these two sets. Now start from some point and run BFS, detect its adjacents, add them to queue and erase them from $F$ and $S$. This leads to a $\mathcal{O}(N \cdot \log N \cdot \log{2 \cdot 10 ^ 9})$ solution which is enough for getting 80 points. Let's use some trick to make the check function faster. Each time you erase something from front or end of some set, mark that but not erase it from another set. After each step, make sure that there isn't any marked point at front or end of the set. So the set is not necessary and you can use deque. This leads to $\mathcal{O}(N \cdot \log{2 \cdot 10 ^ 9})$ solution which is enough for getting full mark. IMPLEMENTATION 
This question is marked "community wiki".
asked 30 Jul '17, 00:19

This can be solved in O(NlogMax) pretty easily answered 30 Jul '17, 01:28

And it can be extended to multiple dimentions with complexity $O(NlogMax2^d)$ as well by considering $2^d$ corner points. answered 30 Jul '17, 01:30

You can also solve this using Manhattan MCST. The smallest edge in your MCST determines the value of D. Consider rotating the plane by 45 degrees, then collect borders of rectangle containing all points. Find a representative from each border (four total), create edges from the representatives to every other point. Get MCST using Prim's or Kruskals, then the minimum edge is the answer. Total complexity is $O(N log N)$. answered 30 Jul '17, 12:15
@hikarico Why are you rotating plane by 45 degree ?
(02 Aug '17, 14:22)

I believe we can answer the question in $O(N)$ time. The idea is that if the graph is connected, then every point is connected to at least one of the 4 corner points (the points with maximal $\pm x \pm y$). First, we connect every point to the farthest corner point in $O(N)$ time. Now, if either every point is connected to one of the $+45^\circ$ corner points, or every point is connected to one of the $45^\circ$ corner points, then the graph is connected, as the same angle corner points are also connected. Otherwise, if we have used corner points of both angles, then we can connect the two corner points of the same angle without decreasing the minimal distance used. We have yet to connect the two components of the graph. We will find the optimal edge connecting the two subsets between a point of one subset and a corner point of the other subset, hence we can find it in $O(N)$ time. answered 30 Jul '17, 17:43

Another simple approach, first use 45 degree rotation for every points to make the unreachable region of each point an axis aligned square. Then, while binary searching the answer, to check a distance $d$ is going to make the whole thing connected or not we have to check that if there exists any special point inside the intersection of all the unreachable square region of all special points. Clearly the intersection will be a axis aligned square or rectangle and it can be found in $O(N)$. And the checking if any point is bounded in the intersection also has the same complexity. Overall complexity $O(Nlog(2*10^9))$. answered 30 Jul '17, 05:12

For what value of D we have to check that graph is connected or not. Do we have to apply binary search on D. Editorial is not clear to me. Please Help. @abhikalpu Can you please explain this more "Another simple approach, first use 45 degree rotation for every points to make the unreachable region of each point an axis aligned square." answered 30 Jul '17, 11:28
