Codeforces Round 951 (Div. 2) |
---|
Закончено |
Манхэттенским расстоянием между двумя точками $$$(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$$$» (без кавычек).
Если существует несколько решений, выведите любое из них.
66 43 10 00 -25 -33 -52 -25 40 00 -25 -33 -52 -26 63 10 00 -25 -33 -52 -24 43 00 3-3 00 -310 82 1-5 -1-4 -1-5 -30 1-2 5-4 4-4 20 0-4 14 400000100000 100000-100000 100000100000 -100000-100000 -100000
2 6 1 4 3 5 3 5 1 0 0 0 6 1 3 0 0 0
В первом наборе входных данных:
В третьем наборе входных данных:
В четвертом наборе входных данных не существует двух точек, манхэттенское расстояние между которыми равно $$$4$$$, а следовательно подходящего манхэттенского треугольника не существует.
Название |
---|