Пустые треугольники
Знаете ли вы, как легко превратить очень простую задачу в невероятно сложную? Вот пример. Сколько треугольников можно построить с помощью N прямых на плоскости? Пока они имеют разные наклоны и никакие три из них не пересекаются в одной точке, будут треугольники, что является максимальным возможным количеством.
Хорошо, это было не так уж плохо. Но давайте посмотрим, что произойдет, если мы будем считать только треугольники, которые пусты (то есть ни одна из линий не проходит через внутреннюю часть треугольника). Тогда количество треугольников внезапно становится очень маленьким. Например, с 4 прямыми линиями мы можем сделать только 2 пустых треугольника, тогда как общее количество треугольников может быть до 4. Обратитесь к диаграмме.
Фактически, общая формула для максимального количества пустых треугольников, которые можно нарисовать с помощью N линий, неизвестна. Однако сложная часть заключается в нахождении правильной конфигурации линий. Ваша задача намного проще; имея N прямых линий на плоскости, подсчитайте количество пустых треугольников.
Входные данные
Входные данные состоят из нескольких тестов. Каждый тест начинается с строки, содержащей целое число N, 1 ≤ N ≤ 500, которое указывает количество линий на плоскости. Следующие N строк содержат по четыре целых числа x_1, y_1, x_2 и y_2 (от −1000 до 1000), представляющих прямую линию, проходящую через (x_1, y_1) и (x_2, y_2). Гарантируется, что никакие три линии не пересекаются в одной точке, и все линии различны. Ввод завершается строкой с N = 0.
Выходные данные
Для каждого теста выведите одну строку, содержащую количество пустых треугольников, образованных данными линиями.