COCI 2006/2007, Contest #2

Task STRAŽA

Near a military base there is a system of trenches, modeled as line segments on a plane. During nighttime, when most soldiers are fast asleep, three guards stand watch of the trenches. Two guards can see each other if there is a trench (or a row of trenches) along the entire straight line segment between them and there is no third guard on that line segment.

For security reasons, the guards must be placed so that each guard sees the other two. How many ways can they be placed?

Input

The first line contains the integer N (1 ≤ N ≤ 20), the number of trenches. Each of the next N lines contains the description of one trench: four positive integers X1, Y1, X2, Y2 (all less than or equal to 1000), where X1 and Y1 are coordinates of one end, while X2 and Y2 are coordinates of the other end of the trench.

Trenches in the input may overlap and share endpoints.

Output

Output the number of ways the guards can be placed on a single line.

Sample Tests

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

8

4
5 1 7 1
1 1 5 1
4 0 4 4
7 0 3 4

1

3
2 2 3 2
3 2 3 3
3 3 2 3

0

All Submissions
Best Solutions

Point Value: 20 (partial)
Time Limit: 1.00s
Memory Limit: 32M
Added: Aug 13, 2013

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)