Manhattan Triangle
Contest: Codeforces Round 951 (Div. 2)
Difficulty rating: 2400
Tags: binary search, constructive algorithms, data structures, geometry, implementation, two pointers

The Manhattan distance between two points $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ is defined as: $$$$$$|x_1 - x_2| + |y_1 - y_2|.$$$$$$

We call a Manhattan triangle three points on the plane, the Manhattan distances between each pair of which are equal.

You are given a set of pairwise distinct points and an even integer $$$d$$$. Your task is to find any Manhattan triangle, composed of three distinct points from the given set, where the Manhattan distance between any pair of vertices is equal to $$$d$$$.

Input format:
Each test consists of multiple test cases. The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$d$$$ ($$$3 \le n \le 2 \cdot 10^5$$$, $$$2 \le d \le 4 \cdot 10^5$$$, $$$d$$$ is even) — the number of points and the required Manhattan distance between the vertices of the triangle.

The $$$(i + 1)$$$-th line of each test case contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^5 \le x_i, y_i \le 10^5$$$) — the coordinates of the $$$i$$$-th point. It is guaranteed that all points are pairwise distinct.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output three distinct integers $$$i$$$, $$$j$$$, and $$$k$$$ ($$$1 \le i,j,k \le n$$$) — the indices of the points forming the Manhattan triangle. If there is no solution, output "$$$0\ 0\ 0$$$" (without quotes).

If there are multiple solutions, output any of them.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first test case:

Points $$$A$$$, $$$B$$$, and $$$F$$$ form a Manhattan triangle, the Manhattan distance between each pair of vertices is $$$4$$$. Points $$$D$$$, $$$E$$$, and $$$F$$$ can also be the answer.

In the third test case:

Points $$$A$$$, $$$C$$$, and $$$E$$$ form a Manhattan triangle, the Manhattan distance between each pair of vertices is $$$6$$$.

In the fourth test case, there are no two points with a Manhattan distance of $$$4$$$, and therefore there is no suitable Manhattan triangle.

Example input:
6
6 4
3 1
0 0
0 -2
5 -3
3 -5
2 -2
5 4
0 0
0 -2
5 -3
3 -5
2 -2
6 6
3 1
0 0
0 -2
5 -3
3 -5
2 -2
4 4
3 0
0 3
-3 0
0 -3
10 8
2 1
-5 -1
-4 -1
-5 -3
0 1
-2 5
-4 4
-4 2
0 0
-4 1
4 400000
100000 100000
-100000 100000
100000 -100000
-100000 -100000

Example output:
2 6 1
4 3 5
3 5 1
0 0 0
6 1 3
0 0 0

Editorial:
Note this fact: in every Manhattan triangle there are two points such that $$$|x_1 - x_2| = |y_1 - y_2|$$$.
Let's start with distributing all points with their $$$(x + y)$$$ value.
For each point $$$(x; y)$$$ find point $$$(x + d / 2; y - d / 2)$$$ using lower bound method in corresponding set. Then we have to find the third point: it can be in either $$$(x + y + d)$$$ or $$$(x + y - d)$$$ diagonal. Borders at $$$x$$$ coordinate for them are $$$[x + d / 2; x + d]$$$ and $$$[x - d / 2; x]$$$ — it can be found using the same lower bound method.
Then, distribute all points with $$$(x - y)$$$ value and do the same algorithm.
Total time complexity is $$$O(n \log n)$$$.