Аксиома Хузиты 6
Первый формальный список аксиом для оригами был опубликован Хумиаки Хузитой и Бенедетто Скимеми и стал известен как аксиомы Хузиты. Эти аксиомы описывают способы создания линии сгиба путем выравнивания точек и линий. Ниже представлена версия шести аксиом.
Для точек p_1 и p_2 существует уникальная линия сгиба, проходящая через обе.
Для точек p_1 и p_2 существует уникальная линия сгиба, которая совмещает p_1 с p_2.
Для линий l_1 и l_2 существует линия сгиба, которая совмещает l_1 с l_2.
Для точки p_1 и линии l_1 существует уникальная линия сгиба, перпендикулярная l_1, проходящая через точку p_1.
Для точек p_1 и p_2 и линии l_1 существует линия сгиба, которая совмещает p_1 с l_1 и проходит через p_2.
Для точек p_1 и p_2 и линий l_1 и l_2 существует линия сгиба, которая совмещает p_1 с l_1 и p_2 с l_2.
Роман — талантливый программист, но он только начинает осваивать искусство оригами. Поэтому он решил создать программу, которая будет вычислять необходимые линии сгиба за него. Он уже реализовал код для первых пяти аксиом, но столкнулся с трудностями при реализации более сложной аксиомы номер 6. Поэтому он решил обратиться за помощью к вашей команде опытных программистов, чтобы вы реализовали этот случай в его программе.
Входные данные
Входные данные состоят из одного или более тестов. Общее количество тестов t указано в первой строке входного файла и не превышает 20000.
Каждый тест состоит ровно из четырех строк, описывающих l_1, p_1, l_2 и p_2, в указанном порядке. Каждая строка содержит четыре целых числа — координаты двух различных точек на линии: x_1, y_1, x_2, y_2. Каждая точка задается двумя целыми числами — её координатами x и y. Все координаты не превышают 10 по абсолютной величине. Гарантируется, что ни p_1 не лежит на l_1, ни p_2 не лежит на l_2. Линии l_1 и l_2 различны, но точки p_1 и p_2 могут совпадать.
Выходные данные
Для каждого теста выведите отдельную строку, описывающую прямую линию, которую следует использовать для сгиба. Используйте тот же формат, что и во входных данных — укажите координаты двух точек на линии. Либо координаты x, либо y этих двух точек должны отличаться как минимум на 10^{−4}. Координаты не должны превышать 10^9 по абсолютной величине. Программа проверки будет проверять, что как расстояние между p_1 после сгиба и l_1, так и расстояние между p_2 после сгиба и l_2 не превышают 10^{−4}. Если существует несколько решений, любое из них подойдет. Если решений нет, выведите строку из четырех нулей, разделенных пробелами.
На рисунке справа иллюстрируется первый пример. Линия сгиба обозначена пунктиром.