| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 7 | 5 | 4 | 66.667% |
Недавно Вася объяснил своему младшему брату Пете основы работы с циркулем и линейкой. В качестве примера он показал, как по данному треугольнику построить такой, что середины его сторон совпадают с вершинами первого. Такое действие он назвал <<расширением>> треугольника.
Например, на рисунке треугольник $DEF$ является расширением треугольника $ABC$.
Для закрепления материала Вася решил дать брату какое-нибудь простое задание на точность построения геометрических фигур. Немного поразмыслив, он нарисовал на листе бумаги $n$ треугольников и назвал <<шагом>> однократное расширение всех треугольников. После этого он попросил Петю узнать, через какое число шагов найдется пара пересекающихся треугольников.
Два треугольника пересекаются, если существует точка, лежащая внутри или на границе каждого треугольника. В частности, если один треугольник находится внутри другого, то такие треугольники пересекаются.
Петя слушал умного брата не очень внимательно, поэтому с первого раза у него ничего не вышло. Тогда Вася заготовил ему еще несколько примеров, а для того, чтобы ему было проще проверять, попросил вас нaписать программу, которая по заданным треугольникам выводит ответ на задачу.
Первая строка входного файла содержит натуральное число $n$ --- количество треугольников (2ドル \le n \le 50$). Следующие $n$ строк содержат по шесть целых чисел --- $x_1, y_1, x_2, y_2, x_3, y_3,ドル разделенных пробелами. Эти величины задают треугольник с вершинами в точках $(x_1, y_1),ドル $(x_2, y_2)$ и $(x_3, y_3)$. Все числа во входном файле не превышают по модулю 10ドル^8$.
В первой строке выходного файла выведите одно целое число --- через какое число шагов найдется пара пересекающихся треугольников.
2 0 0 1 0 0 1 0 0 -1 0 0 -1
0
2 0 0 1 0 0 1 -1 -1 -1 3 3 -1
0
2 10 2 5 9 3 5 -9 0 0 -9 -9 -5
3
Пояснение для последнего примера:
Сплошными линиями обозначены расширения первого треугольника, пунктирными --- второго.