Задача R. Треугольные конфигурации

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:16 Мб
Выходной файл:output.txt  

Условие

Рассмотрим некоторую заданную конфигурацию n прямых на плоскости. Требуется подсчитать максимальное число не перекрывающихся между собой треугольников, образованных в результате их пересечения.

Примечание

Следует обратить внимание на то, что решение задачи крайне чувствительно к погрешностям округления. Для обхода данной проблемы рекомендуется, по возможности, использовать дробную арифметику.

Формат входного файла

Во входном файле "input.txt" записано натуральное число n, за которым следует ровно n прямых. Каждая прямая задается парой несовпадающих точек: (axi, ayi), (bxi, byi).

Формат выходного файла

Выходной файл "output.txt" должен содержать число полученных треугольников.

Ограничения

Гарантируется, что никакие две прямые не совпадают между собой.

Все входные значения являются целыми десятичными числами.

104 ≤ (axi, ayi, bxi, byi) ≤ 104, 3 ≤ n ≤ 300

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
5
  0 -20  15 -20
-10  10  35 -35
  0   0   0 -10
-10   0  30   0
-20   0   0  20
3
2
5
-10   0   0 -20
-20 -10 -10 -30
  0   0  10  24
  0  10  10 -10
-10   0   0  24
0

0.120s 0.021s 17