Задача 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.080s 0.010s 15