[COCI2006-2007#2] STRAZA

题目描述： 在军事基地附近有一个战壕场，其中的战壕以平面上的线段为模型。在夜间，当大多数士兵熟睡的时候，三个警卫站在战壕旁边。如果在它们之间的整个直线段上有一条战壕（或一排战壕），且该直线段上没有第三警卫，那么两个警卫可以看到彼此。出于安全原因，必须安排警卫，以便每名警卫看到另外两名警卫。它们有多少种被安排的方式？ 输入格式： 第一行包含整数n（1≤n≤20），战壕的数目。接下来的n行中的每一行都包含一个战壕的描述：四个正整数X1,Y1,X2,Y2（都小于或等于1000），其中X1和Y1是一端的坐标，而X2和Y2是战壕另一端的坐标。输入中的战壕可能重叠并共享端点。 输出格式： 在这一行中，有多少种安排警卫的方式。

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?

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 the number of ways the guards can be placed on a single line.

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