Military Base

Time limit1sMemory limit128 MB

Summary
Given up to 20 line-segment trenches, count unordered triples of intersection/endpoint points that are mutually visible along the trench network, meaning every pair's connecting segment lies fully on the union of trenches and no third point lies strictly between them.
Level

Hard8 of 10

Topics
Geometry, Graph, Brute force
Solved
No attempts yet

Problem

Several trenches lie on a plane. Each trench is represented by a line segment. A soldier can be placed at any trench endpoint or at any point where two trenches meet or cross.

At night, exactly three soldiers are placed at three distinct positions. Two soldiers can see each other if the whole segment connecting them lies on the union of the trenches. If the third soldier lies strictly between those two soldiers on that segment, then those two soldiers cannot see each other.

For security, every pair among the three soldiers must be able to see each other. Count the number of possible placements. The three soldiers are not distinguished from one another.

Input

The first line contains the number of trenches N (1 <= N <= 20).

Each of the next N lines contains four integers X1 Y1 X2 Y2, describing the two endpoints (X1, Y1) and (X2, Y2) of one trench. Every coordinate is an integer from 0 to 1000, inclusive.

Trenches may overlap and may share endpoints.

Output

Print the number of possible placements for the three soldiers.

Examples3

  1. Example 1

    Input
    6
0 0 1 0
0 0 0 1
1 0 1 1
0 1 1 1
0 0 1 1
1 0 0 1
    Expected output
    8

  2. Example 2

    Input
    4
5 1 7 1
1 1 5 1
4 0 4 4
7 0 3 4
    Expected output
    1

  3. Example 3

    Input
    3
2 2 3 2
3 2 3 3
3 3 2 3
    Expected output
    0