Problem L. Lines and triangles ≡

Author:A. Baranov   Time limit:1 sec
Input file:Standard input   Memory limit:256 Mb
Output file:Standard output  

Statement

Let's consider a configuration of n lines on a plane. The task is to count the maximum number of triangle cells formed as a result of subdivison plane by these lines.

Input format

The input begins with a natural number n, followed by exactly n lines. Each line is defined by a pair of distinct points: (Axi, Ayi), (Bxi, Byi).

Output format

The output should contain the number of triangles obtained.

Constraints

It is guaranteed that no two lines coincide.

All input values are integers.

 − 104 ≤ (Axi, Ayi, Bxi, Byi) ≤ 104, 3 ≤ n ≤ 300

Sample tests

No. Standard input Standard output
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

Explanation

Для начала найдем все попарные пересечения имеющихся прямых.

Каждая i-я прямая задается параметрическим уравнением:
{ Xi(p) = Axi + p ⋅ (Bxi − Axi); Yi(p) = Ayi + p ⋅ (Byi − Ayi). .

Для того, чтобы найти точку пересечения двух таких прямых, нам потребуется решить систему уравнений:
{ Xi(pi) = Xj(pj); Yi(pi) = Yj(pj), .
где (pi, pj) — параметры, задающие положение точки на i-й и j-й прямой соответственно.

Такая система либо не имеет решения (если прямые параллельны), либо имеет единственное решение.

Во избежание погрешностей округления, здесь также можно задействовать рациональную арифметику.

Полученные точки пересечения формируют вершины некоторого планарного графа,
а проведенные через них отрезки прямых — его ребра.

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

Путем последовательного обхода таких массивов можно сформировать списки смежности вершин.

Следующий этап заключается в подсчете циклов, состоящих из трех вершин.

Для этой цели задействуем обход в глубину.

При этом, во избежание повторного включения ранее просмотренных циклов,
можно установить правило, по которому
обход вершин должен осуществляться по возрастанию их индексов/адресов.
Т.е. из k-й вершины можно будет перейти
в l-ю вершину, только если k < l.

0.077s 0.008s 15