← 返回题目列表

Codeforces · 1979/E

E. 曼哈顿三角

中文机器翻译题面 查看原题

两点 $$$(x_1, y_1)$$$ 和 $$$(x_2, y_2)$$$ 之间的曼哈顿距离定义为: $$$$$$|x_1 - x_2| + |y_1 - y_2|.$$$$$$

我们将平面上的三个点称为曼哈顿三角形,每对点之间的曼哈顿距离相等。

给你一组成对的不同点和一个偶数 $$$d$$$。您的任务是找到由给定集合中的三个不同点组成的任意曼哈顿三角形,其中任意一对顶点之间的曼哈顿距离等于 $$$d$$$。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$d$$$ ($$$3 \le n \le 2 \cdot 10^5$$$, $$$2 \le d \le 4 \cdot 10^5$$$, $$$d$$$ 为偶数) — 点数和三角形顶点之间所需的曼哈顿距离。

每个测试用例的第 $$$(i + 1)$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$-10^5 \le x_i, y_i \le 10^5$$$) — 第 $$$i$$$ 个点的坐标。保证所有点都是成对不同的。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出三个不同的整数 $$$i$$$、$$$j$$$ 和 $$$k$$$ ($$$1 \le i,j,k \le n$$$) — 构成曼哈顿三角形的点的索引。如果无解,则输出“$$$0\ 0\ 0$$$”(不带引号)。

如果有多个解,则输出其中任意一个。

示例

输入 #1

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

输出 #1

2 6 1
4 3 5
3 5 1
0 0 0
6 1 3
0 0 0

注意

在第一个测试用例中:

点$$$A$$$、$$$B$$$和$$$F$$$构成曼哈顿三角形,每对顶点之间的曼哈顿距离为$$$4$$$。点 $$$D$$$、$$$E$$$ 和 $$$F$$$ 也可以是答案。

在第三个测试用例中:

点$$$A$$$、$$$C$$$和$$$E$$$构成曼哈顿三角形,每对顶点之间的曼哈顿距离为$$$6$$$。

在第四个测试用例中,不存在曼哈顿距离为 $$$4$$$ 的两个点,因此不存在合适的曼哈顿三角形。