题目描述

来自古董与奇珍博物馆（ACM）的考古学家们已经飞往埃及，去研究凯奥普斯（Key-Ops）金字塔。利用最先进的技术，他们能够确定金字塔底层是由一系列直线墙壁构成的，这些墙壁相互交叉形成了许多封闭的房间。目前，没有任何门可以进入任何一个房间。这种最先进的技术还精确定位了宝藏室的位置。这些敬业（且贪婪）的考古学家想要炸开墙壁上的门以进入宝藏室。然而，为了尽量减少对中间房间内艺术品的损坏（并且不超出他们的炸药政府拨款），他们希望炸开的门数量最少。出于结构完整性考虑，门只能在进入的房间墙壁的中点炸开。你需要编写一个程序来确定这个最少的门的数量。

下面是一个示例：

输入

输入将包含一个测试用例。第一行是一个整数 $n$（$0 \leq n \leq 30$），表示内部墙壁的数量，接下来的 $n$ 行每行包含一组整数，表示每堵墙的端点坐标 $x_1 y_1 x_2 y_2$。金字塔的四堵外围墙的端点是固定的，分别为 $(0,0)$、$(0,100)$、$(100,100)$ 和 $(100,0)$，这些墙不包含在墙壁列表中。内部墙壁总是从一堵外墙延伸到另一堵外墙，并且排列方式使得任何交点最多只有两堵墙相交。你可以假设没有任何两堵给定的墙是重合的。在列出内部墙壁之后，将有一行包含宝藏室的浮点坐标（保证不会位于墙上）。

输出

打印一行，列出需要创建的最少门的数量，格式如下所示。

输入数据 1

7 
20 0 37 100 
40 0 76 100 
85 0 0 75 
100 90 0 90 
0 71 100 61 
0 14 100 38 
100 47 47 100 
54.5 55.4 

输出数据 1

Number of doors = 2

来源

北美东部中部 1999