Treasure Hunt

题面翻译

题目描述

考古学家考察金字塔。金字塔的底层是由一系列直线墙构成的，这些直线墙相交形成许多封闭的房间。目前，没有门存在以允许进入任何房间。这项技术也精确定位了宝藏室的位置。

考古学家想通过炸门进入宝藏室。他们想炸门的数量最少。只能在墙壁的中点对门进行爆破。求炸门的最小数目。

下图是一个例子。

输入格式

有多组输入。输入的第一行是数据组数。每组输入的第一行是一个整数 $n$ ，指定内墙的数量，以下 $n$ 行是墙的整数端点$x_1$ $y_1$ $x_2$ $y_2$。金字塔的4个围墙在 $(0,0)$,$(0,100)$,$(100,100)$,$(100,0)$ 处有固定的端点，不在输入的围墙列表中。内墙总是从一个外墙跨越到另一个外墙，没有三个及以上堵墙交于一点。你可以假设没有两堵墙重合。内墙挂牌后，最后一行将包含宝藏室中宝藏的浮点坐标（保证不与墙重合）。

每组输入之间用空行隔开。

输出格式

对于每种情况，输出一行，即需要炸门的最小数量，格式见样例。

每两组输出之间用空行隔开。

数据范围

$0\le n\le 30$

题目描述

PDF

输入格式

输出格式

样例 #1

样例输入 #1

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