**PROBLEM LINK** -

Author and Editoriallist - AmirReza PoorAkhavan

Tester - MohammadSina Pakseresht

Second Tester - Shayan CheshmJahan

**DIFFICULTY** –

**PREREQUISITES** –

Binary-search.

**EXPLANATION** –

Let’s use binary-search, 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:

- P + Q \geq X + Y + D \Rightarrow P - X + Q - Y \geq D \Rightarrow |P - X| + |Q - Y| \geq D
- P + Q \leq X + Y - D \Rightarrow P - X + Q - Y \leq -D \Rightarrow |P - X| + |Q - Y| \geq D
- P - Q \geq X - Y + D \Rightarrow P - Q - X + Y \geq D \Rightarrow |P - X| + |Q - Y| \geq D
- P - Q \leq X - Y - D \Rightarrow P - Q - X + Y \leq -D \Rightarrow |P - X| + |Q - Y| \geq D

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** -

Author’s code - here.

Second tester’s code - here.