Треугольники и Четырехугольник
Маленькой Юань всего два года, и она изучает треугольники и четырехугольники. Она такая умная девочка, что вскоре понимает: два треугольника могут образовать четырехугольник, не перекрывая друг друга. Она берет много треугольников и пытается из них составить четырехугольники. К сожалению, она не всегда справляется с этой задачей и иногда допускает ошибки.
Как ее брат, вы хотите выяснить, допустила ли она ошибку при попытке составить четырехугольник из двух треугольников. Вы решили написать программу, которая поможет определить это.
Учтите, что в этой задаче четырехугольник определяется как простой многоугольник с четырьмя вершинами. Вы также можете предположить, что все треугольники и четырехугольники имеют положительную площадь.
Обратите внимание, что два графа считаются одинаковыми, если их можно полностью наложить друг на друга с помощью сдвига, вращения и отражения. Вы также можете сдвигать, вращать и отражать один из треугольников, чтобы составить из них четырехугольник.
Входные данные
Входные данные содержат несколько тестов. Первая строка содержит одно целое число T, обозначающее количество тестов. (T ≤ 500)
Для каждого теста предоставляется ровно 10 строк.
Первые 3*2 строки описывают два треугольника. Каждая строка содержит два целых числа, обозначающих координаты точки.
Следующие 4 строки описывают четырехугольник, заданный по часовой стрелке или против часовой стрелки.
Все координаты по модулю меньше 15000.
Выходные данные
Для каждого теста выведите "Yes", если данные треугольники могут образовать четырехугольник без перекрытия, и "No" в противном случае.