This task has a pretty cool "visual" solution.

For this part let's suppose that $$$d = 4$$$ (desirable distance between each pair of points)

In the picture below you can see $$$2$$$ points: $$$\color{#A00}{A}$$$ and $$$\color{#00A}{B}$$$. All points that are at a Manhattan distance of $$$4$$$ from point $$$\color{#A00}{A}$$$ are located on the red square, all points that are at a Manhattan distance of $$$4$$$ from point $$$\color{#00A}{B}$$$ are located on the blue square. With $$$\color{#A00}{1},\color{#A00}{2},\color{#A00}{3},\color{#A00}{4}$$$ I numbered the corners of the red square, and $$$\color{green}{C}$$$, $$$\color{green}{D}$$$ are the intersection points of red and blue squares.

1) Let's suppose point $$$\color{#A00}{A}$$$ is one of the points we want to take. (So it is one of the three points, that have the same Manhattan distance to each other)

2) If we also want to take $$$\color{#00A}{B}$$$, then Manhattan distance from $$$\color{#A00}{A}$$$ to $$$\color{#00A}{B}$$$ should be $$$d = 4$$$ => point $$$\color{#00A}{B}$$$ should be on the edge of the red square.

3.1) If point $$$\color{#00A}{B}$$$ lies on side $$$[\color{#A00}{1},\color{#A00}{4}]$$$ or $$$[\color{#A00}{2},\color{#A00}{3}]$$$, blue square will go through the exact middle of either $$$[\color{#A00}{1},\color{#A00}{2}]$$$ or $$$[\color{#A00}{3},\color{#A00}{4}]$$$ side.

3.2) If point $$$\color{#00A}{B}$$$ lies on side $$$[\color{#A00}{1},\color{#A00}{2}]$$$ or $$$[\color{#A00}{3},\color{#A00}{4}]$$$, blue square will go through the exact middle of either $$$[\color{#A00}{1},\color{#A00}{4}]$$$ or $$$[\color{#A00}{2},\color{#A00}{3}]$$$ side.

4) The third point should have distance $$$d$$$ to both points $$$\color{#A00}{A}$$$ and $$$\color{#00A}{B}$$$. It means that it should lie both on the red and blue squares. Point $$$\color{green}{C}$$$ is one of such points. Notice that it also lies in the middle of the side $$$[\color{#A00}{1},\color{#A00}{2}]$$$.

5) Let's summarize 3-4: pick a point $$$\color{#A00}{A}$$$, pick some other point $$$\color{#00A}{B}$$$ that is on red square. Find the intersection points, one of them (in our case it is point $$$\color{green}{C}$$$) will always lie in the middle of one of the sides of the red square.

This means that no matter what $$$3$$$ points we take, one of them will always lie in the middle of one of the sides of the "Manhattan squares" that we draw around points. (In the picture above point $$$\color{green}{D}$$$ does not lie in the middle of any of the sides of the red square. But notice that it lies in the middle of blue square side)

We can think about it like this. Let's take $$$3$$$ points. Let's name them in a way, so that if we draw a red square around point $$$\color{#A00}{A}$$$, point $$$\color{green}{C}$$$ will lie in the middle of one of the sides of the red square.

If we define points $$$\color{#A00}{A}$$$ and $$$\color{green}{C}$$$ like this, it would mean that if we fixate the position of point $$$\color{#A00}{A}$$$, there are only $$$4$$$ possibilities where point $$$\color{green}{C}$$$ might be (there are $$$4$$$ sides of the red square, and point $$$\color{green}{C}$$$ could be in the middle of any of them). This is the key to our solution.

Let $$$\color{green}{C_1}$$$, $$$\color{green}{C_2}$$$, $$$\color{green}{C_3}$$$, $$$\color{green}{C_4}$$$ be all of the possible positions of point $$$\color{green}{C}$$$.

6) Let's suppose we picked option $$$\color{green}{C_1}$$$. Is it possible to figure out where point $$$\color{#00A}{B}$$$ might be? It could only be at the intersection of green square and red square. So point $$$\color{#00A}{B}$$$ might be either on $$$[\color{green}{C_2},\color{#A00}{2}]$$$ segment or $$$[\color{green}{C_4},\color{#A00}{3}]$$$ segment

This is where theoretical part of the solution ends and annoying implementation begins. We iterate through all of the points $$$\color{#A00}{A}$$$, check for existence of points $$$\color{green}{C_1}$$$,$$$\color{green}{C_2}$$$,$$$\color{green}{C_3}$$$,$$$\color{green}{\color{green}{C_4}}$$$. And for each one of them that exists, we try to find point $$$\color{#00A}{B}$$$ on the needed segments. We can store points on each diagonal (lines that are parallel to $$$[\color{#A00}{1},\color{#A00}{2}]$$$ and $$$[\color{#A00}{3},\color{#A00}{4}]$$$ or parallel to $$$[\color{#A00}{1},\color{#A00}{4}]$$$ and $$$[\color{#A00}{2},\color{#A00}{3}]$$$) in a sorted way, and search for point $$$\color{#00A}{B}$$$ with binary search. I don't want to go into details, because the point of this blog is to provide you with an easier approach than this one. But if you are really interested, here is my implementation.

0) To make the editorial text easier to read, let me introduce a new definition

• Let's imagine 2 points $$$A(s_1, t_1)$$$, $$$B(s_2,t_2)$$$
• Let's say they have Manhattan distance between them equal to $$$d$$$
• if $$$|s_1-s_2| = d$$$, let's say these 2 points are $$$\texttt{s-distant}$$$
• if $$$|t_1-t_2| = d$$$, let's say these 2 points are $$$\texttt{t-distant}$$$
• note, that 2 points can be both $$$\texttt{s-distant}$$$ and $$$\texttt{t-distant}$$$ simultaneously.

1) 3 points that have Manhattan distance equal $$$d$$$ to each other cannot be all $$$\texttt{s-distant}$$$ or all $$$\texttt{t-distant}$$$. It is easy to prove:

• lets suppose the opposite, that there are some 3 points that are $$$\texttt{s-distant}$$$.
• Lets say these 3 points have $$$s_1 \leq s_2 \leq s_3$$$ coordinates.
• If they are all $$$\texttt{s-distant}$$$ , it would mean that $$$s_2-s_1 = d \texttt{ and } s_3-s_2 = d \texttt{ and } s_3-s_1 = d$$$

It is clear to see that it is impossible to satisfy this equation for positive $$$d$$$, so it means that 3 points cannot all be $$$\texttt{s-distant}$$$.

2) If all 3 pairs cannot be $$$\texttt{s-distant}$$$, it means that some pairs are $$$\texttt{s-distant}$$$, and some are $$$\texttt{t-distant}$$$. Let's suppose that points $$$A(s_1, t_1)$$$, $$$B(s_2, t_2)$$$ are the only $$$\texttt{s-distant}$$$ pair and go from there.

3) Let's say that point $$$A$$$ has the smaller coordinate $$$s$$$, it would mean that

• $$$s_2 = s_1+d$$$
• $$$B(\color{green}{s_1+d}, t_2)$$$

4) Point $$$C(s_3, t_3)$$$ should be $$$\texttt{t-distant}$$$ with both points $$$A$$$ and $$$B$$$. (Because as we defined in 2, $$$A$$$,$$$B$$$ is the only pair of points that is $$$\texttt{s-distant}$$$). It means that:

• $$$|t_1-t_3| = d$$$
• $$$|t_2-t_3| = d$$$

It is only possible when $$$t_1 = t_2$$$.

• $$$B(s_1+d, \color{green}{t_1})$$$

5) $$$C$$$ is $$$\texttt{t-distant}$$$ with both points $$$A$$$ and $$$B$$$. That means $$$|t_3 - t_1| = d$$$. But we don't know exactly whether $$$t_3$$$ is smaller or bigger than $$$t_1$$$. We can put it this way:

• $$$t_3 = t_1 \pm d$$$

• $$$C(s_3, \color{green}{t_1 \pm d})$$$

6) So for now we have 3 points

• $$$A(s_1, t_1)$$$

• $$$B(s_1+d, t_1)$$$

• $$$C(s_3, t_1 \pm d)$$$

We were able to use only variables $$$s_1$$$, $$$t_1$$$ and $$$s_3$$$ (and $$$d$$$) to define all points. There are some things that we can say about $$$s_3$$$

• If $$$s_3 < s_1$$$, then distance between $$$B$$$, $$$C$$$ becomes $$$>d$$$ (because $$$s_1+d - s_3 > d$$$, when $$$s_3 < s_1$$$). This should not happen, because we want all of the distances to be equal to $$$d$$$
• If $$$s_3 > s_1+d$$$, then distance between $$$A$$$, $$$C$$$ becomes $$$>d$$$ (because $$$s_3 - s_1 > d$$$, when $$$s_3 > s_1 + d$$$).

So it means that $$$s_1 \leq s_3 \leq s_1+d$$$

7) Notice that we can repeat all of the steps 2-5 by assuming that points A, B are the only $$$\texttt{t-distant}$$$ pair. All of the steps would be identical, just swap t and s

We are ready to think about the implementation.

Implementation plan

1) Apply trick and turn all of the points into $$$(s, t)$$$ form

2) Let's iterate through all points and treat them as $$$A(s_1, t_1)$$$

3) Let's check for existence of point $$$B(s_1+d, t_1)$$$

4) if it exists, let's search for a point $$$C(s_3, t_1 \pm d)$$$, where $$$s_3 \in [s_1, s_1+d]$$$. We can search for this point by storing all of the points with the same $$$t$$$ coordinate in sorted arrays, and using binary search to search for a suitable $$$s_3$$$ value.

5) Repeat the above steps, but swap coordinates $$$s$$$ and $$$t$$$ for every point.

Here is my implementation of this approach

We transform coordinates the following way:

• $$$s = x + y$$$
• $$$t = x - y$$$

Because of it one new property suddenly appears: let's analyze the value $$$s+t$$$

• $$$s+t = x+y + x - y = 2x$$$ => $$$s+t$$$ is always even

So after transforming points from $$$XY$$$ coordinate system, where $$$x, y$$$ are non decimal numbers, their positions in $$$ST$$$ coordinates will always be "even" (in other words value $$$s+t$$$ will always be even).

That is why our new picture looks twice as big compared to the original: we have "empty" positions in coordinates where $$$s+t$$$ is odd.

I will be brief in this part, it just just plain algebra, and there is quite a lot of it.

so we had a formula $$$dist = |x_1 - x_2| + |y_1 - y_2|$$$, and we want to represent it in terms of $$$s$$$ and $$$t$$$, where $$$s=x+y$$$, $$$t=x-y$$$

1) The first step should be to try representing $$$x$$$ using $$$s$$$ and $$$t$$$ and also do it for $$$y$$$. We can do it the following way:

• $$$s+t = x+y + x - y = 2x$$$
• $$$x = \frac{s+t}{2}$$$
• $$$s-t = x+y - x + y = 2y$$$
• $$$y = \frac{s-t}{2}$$$

2) Let's rewrite the original formula

• $$$dist = |x_1 - x_2| + |y_1 - y_2|$$$
• $$$x_1 = \frac{s_1 + t_1}{2}$$$ , $$$x_2 = \frac{s_2 + t_2}{2}$$$, $$$y_1 = \frac{s_1 - t_1}{2}$$$ , $$$y_2 = \frac{s_2 - t_2}{2}$$$
• $$$dist = |\frac{s_1 + t_1}{2} - \frac{s_2 + t_2}{2}| + |\frac{s_1 - t_1}{2} - \frac{s_2 - t_2}{2}|$$$
• $$$2 * dist = |s_1 + t_1 - s_2 - t_2| + |s_1 - t_1 - s_2 + t_2|$$$
• $$$2 * dist = |(s_1 - s_2) + (t_1 - t_2)| + |(s_1 - s_2) - (t_1 - t_2)|$$$

3) It can be shown that $$$|a+b| + |a-b| = 2*max(|a|, |b|)$$$.

We can prove it by considering 2 cases:

• a) $$$|a| \geq |b|$$$
• $$$|a| \geq |b|$$$ => $$$2*max(|a|, |b|) = 2|a|$$$
• if $$$(a \geq 0 \texttt{ and } b \geq 0) \texttt{ or } (a < 0 \texttt{ and } b < 0)$$$ => $$$|a+b| + |a-b| = (|a|+|b|) + (|a|-|b|) = 2|a|$$$
• if $$$(a \geq 0 \texttt{ and } b < 0) \texttt{ or } (a < 0 \texttt{ and } b \geq 0)$$$ => $$$|a+b| + |a-b| = (|a|-|b|) + (|a|+|b|) = 2|a|$$$

• b) $$$|a| < |b|$$$
• $$$|a| < |b|$$$ => $$$2*max(|a|, |b|) = 2|b|$$$
• if $$$(a \geq 0 \texttt{ and } b \geq 0) \texttt{ or } (a < 0 \texttt{ and } b < 0)$$$ => $$$|a+b| + |a-b| = (|a|+|b|) + (-|a|+|b|) = 2|b|$$$
• if $$$(a \geq 0 \texttt{ and } b < 0) \texttt{ or } (a < 0 \texttt{ and } b \geq 0)$$$ => $$$|a+b| + |a-b| = (-|a|+|b|) + (|a|+|b|) = 2|b|$$$

4) By using 3 we get

• $$$2 * dist = 2*max(|s_1 - s_2|, |t_1 - t_2|)$$$
• $$$dist = max(|s_1 - s_2|, |t_1 - t_2|)$$$

Let's take a random point $$$\color{#A00}{A}$$$, and put it into $$$ST$$$ coordinate system. All of the points that have Manhattan distance of $$$d = 4$$$ to the point $$$\color{#A00}{A}$$$ will exist somewhere on the red square.

If we want point $$$\color{#00A}{B}$$$ to have a distance $$$d = 4$$$ to $$$\color{#A00}{A}$$$, it should be on the red square.

All of the points that have Manhattan distance of $$$d = 4$$$ to the point $$$\color{#00A}{B}$$$ will exist somewhere on the blue square.

Red and blue squares have $$$2$$$ intersection points, lets call them $$$\color{green}{C_1}$$$ and $$$\color{green}{C_2}$$$

We can see, that no matter where we put point $$$\color{#00A}{B}$$$, blue square will always intersect red square on that side, where point $$$\color{#00A}{B}$$$ is.

In our case, we put $$$\color{#00A}{B}$$$ on the right side of the red square, and blue square intersects the right side in the point $$$\color{green}{C_1}$$$.

In other words, no matter where we put $$$\color{#00A}{B}$$$, either/and $$$\color{green}{C_1}$$$ or $$$\color{green}{C_2}$$$ will always share a coordinate $$$s$$$ or $$$t$$$ with point $$$\color{#00A}{B}$$$.

So no matter what points we decide to take (so that they have the same Manhattan distance to each other) $$$2$$$ of them will always have a common $$$s$$$ or $$$t$$$ coordinate.

So if points $$$\color{#00A}{B}$$$ $$$\color{green}{C}$$$ share a coordinate $$$s$$$ or $$$t$$$, and we fix the position of point $$$\color{#00A}{B(s_1, t_1)}$$$, then there are $$$4$$$ options of where point $$$\color{green}{C}$$$ might be.

• $$$C(s_1+d, t_1)$$$
• $$$C(s_1-d, t_1)$$$
• $$$C(s_1, t_1+d)$$$
• $$$C(s_1, t_1-d)$$$

The only point that is unclear for now is point $$$\color{#A00}{A}$$$. We can draw a picture and it will help us to locate it.

In the picture below I chose a case where points $$$\color{#00A}{B}$$$ and $$$\color{green}{C}$$$ share a common coordinate $$$s = 4$$$. Blue square represents all of the points that have Manhattan distance = $$$4$$$ to point $$$\color{#00A}{B}$$$. And Green square represents all of the points that have Manhattan distance = $$$4$$$ to point $$$\color{green}{C}$$$.

In the picture it is clear to see that point $$$\color{#A00}{A}$$$ should have coordinate $$$s$$$ equal to $$$0$$$ or $$$8$$$, and in both cases, coordinate $$$t$$$ should be from $$$0$$$ to $$$4$$$

So in general, if we have 2 points $$$\color{#00A}{B(s_1, t_1)}$$$, $$$\color{green}{C(s_1, t_1+d)}$$$ that share the same coordinate $$$s_1$$$, then point $$$\color{#A00}{A(s_3, t_3)}$$$ should have:

• $$$s_3 = s_1 \pm d$$$
• $$$t_1 \leq t_3 \leq t_1+d$$$

We are ready to think about implementation.

Implementation plan

0) We transform all of the points to $$$ST$$$ system.

1) We pick a point $$$B(s, t)$$$

2) We go through $$$4$$$ options of where point $$$C$$$ might be $$$(s, t \pm d)$$$ or $$$(s \pm d, t)$$$

3.1) If points $$$B$$$ and $$$C$$$ share the same coordinate $$$s$$$, then point $$$A$$$ should have coordinates $$$A(s \pm d, min(t_B, t_C) \leq t_A \leq max(t_B, t_C))$$$

3.2) If points $$$B$$$ and $$$C$$$ share the same coordinate $$$t$$$, then point $$$A$$$ should have coordinates $$$A(min(s_B, s_C) \leq s_A \leq max(s_B, s_C), t \pm d)$$$

4) We can store all points with common coordinate $$$s$$$ in sorted arrays, and search for values $$$t-d$$$ and $$$t+d$$$ with binary search. The same goes for the reverse case.

Here is my implementation of this approach.