Задача №3894. Освещение двора
Фирма, в которой всё ещё работает ваш друг, собирается расширяться на новые маршруты, и потому приобрела
новую площадку для ночного отстоя автобусов. Площадка раньше относилась к военной части, поэтому
она имеет необычную форму — форму треугольника, огороженного забором.
Для того, чтобы освещать площадку ночью, на ней надо установить несколько прожекторов. К счастью, у фирмы как раз в наличие есть три регулируемых прожектора, а на территории площадки обнаружились три высоких столба. Было решено на каждый столб повесить по прожектору и отрегулировать их так, чтобы каждый прожектор освещал ровно одну из трёх сторон забора: один прожектор должен освещать одну сторону забора, другой — другую, третий — третью. Никакой прожектор не должен освещать ни миллиметра “чужой” стены.
Конечно, прожекторы должны освещать не только забор, но вообще всю территорию площадки, поэтому возникла проблема: надо определить, какой прожектор на какую сторону забора направить. Зная ваши высокие навыки в решении подобных задач, фирма обратилась к вам за помощью. Напишите программу, которая будет решать эту задачу.
Естественно, каждый прожектор освещает не только стену, но и всю соответствующую часть двора — треугольник с вершиной в месте, где находится столб, на котором висит прожектор, и основанием, совпадающим с соответствующей стороной забора. Будем считать, что стороны этого треугольника тоже освещены прожектором. Тенью от столбов пренебрегайте.
Первая строка входного файла содержит одно число \(T\) — количество тестовых примеров, которые идут дальше (\(1\leq T\leq 1000\)).
Далее следуют описания \(T\) примеров. В каждом сначала идут шесть чисел \(x_1\), \(y_1\), \(x_2\), \(y_2\), \(x_3\), \(y_3\) — координаты вершин площадки, после чего идут шесть чисел \(X_1\), \(Y_1\), \(X_2\), \(Y_2\), \(X_3\), \(Y_3\) — координаты столбов. Гарантируется, что все столбы находятся строго внутри площадки. Гарантируется, что площадь площадки строго больше нуля. Гарантируется, что никакие два столба не совпадают. Все координаты во входном файле целые и не превосходят по модулю \(800\).
Выведите в выходной файл \(T\) строк по три числа в каждой: для каждого примера выведите номер стороны забора, на которую должен светить прожектор, находящийся на первом столбе, потом номер стороны, на которую должен светить прожектор со второго столба, и наконец номер стороны, на которую должен светить прожектор с третьего столба.
Первая сторона — та, которая соединяет вершины \((x_1, y_1)\) и \((x_2, y_2)\), вторая — \((x_2, y_2)\) и \((x_3, y_3)\), третья — \((x_3, y_3)\) и \((x_1, y_1)\).
Если решения не существует, выведите в соответствующую строку выходного файла три минус единицы:
“-1 -1 -1”.
Первый пример соответствует рисунку.
Среди тестов будут такие, в которых \(T\leq 10\); суммарная стоимость таких тестов будет 70 баллов.
2 0 0 6 10 12 4 7 4 6 6 8 5 -10 -10 0 10 10 -10 0 1 0 -1 1 1
2 3 1 3 2 1