UVa 10979

From Algorithmist
Jump to navigation Jump to search

10979 - How Many Triangles?[edit]

Summary[edit]

N line segments are drawn on the plane. How many triangles are there, whose sides are parts of given line segments?

Explanation[edit]

One way to solve this problem is to construct a planar graph from given line segments, and find the number of 3-cliques in it (see UVa 10973 for this kind of graph problem.)

The graph's vertices are the endpoints of line segments and the points of intersection of segments. Two vertices are connected by an edge, if they both lie on the same line segment.

Some of the graph's cliques correspond to triangles with zero area (which must not be counted.) You can count the number of such cliques separately for each given line segment (beware of overlapping segments), and subtract this number from the total number of 3-cliques.

Implementations[edit]

Input[edit]

10
-5 4 5 -4
-5 4 -6 -1
-5 -3 -1 4
-5 -3 5 3
-5 -3 7 0
-1 4 6 -2
0 0 6 -2
6 -2 5 3
7 0 5 -4
-6 -1 3 -1

Output[edit]

29