Description

摩尔定律指出，芯片上的晶体管数量每两年会翻一番。令人惊讶的是，这一定律在过去半个世纪中一直成立。每当当前技术无法再支持更多增长时，研究人员就会提出新的制造技术，以便将电路打包得更密集。在不久的将来，这可能意味着芯片将以三维而非二维构建。但对于这个问题，二维已经足够了。

所有二维硬件设计（例如芯片、显卡、主板等）中常见的问题是布线。当导线在硬件上布线时，如果它们必须相互交叉，就会出现问题。当发生交叉时，必须使用特殊装置以允许两根电线相互通过，这使得制造成本更高。

我们的问题如下：给定一个已经布置了几根导线的硬件设计（所有导线都是直线段）。还给定一个新的导线连接的起点和终点。你需要确定为了连接起点和终点，必须交叉的现有导线的最小数量。这个连接不需要是直线。唯一的要求是它不能在两个或多个导线已经相交或相遇的点上交叉。

图 1：第一个样例输入

图 1 显示了第一个样例输入。八根现有导线形成了五个正方形。新连接的起点和终点分别位于最左边和最右边的正方形中。黑色虚线表明直接连接将交叉四根导线，而最优解仅交叉两根导线（蓝色曲线）。

Input Format

输入由一个测试用例组成。第一行包含五个整数 $m, x_0, y_0, x_1, y_1$，分别表示已有导线的数量（$m \le 100$）以及需要连接的起点和终点。接下来是 $m$ 行，每行包含四个整数 $x_ a, y_ a, x_ b, y_ b$，描述了一根从 $(x_ a, y_ a)$ 到 $(x_ b, y_ b)$ 的非零长度的现有导线。每个输入坐标的绝对值小于 $10^5$。每对导线最多有一个公共点，即导线不重叠。新导线的起点和终点不位于已有导线上。

Output Format

输出连接起点和终点所需交叉的最小导线数量。

8 3 3 19 3
0 1 22 1
0 5 22 5
1 0 1 6
5 0 5 6
9 0 9 6
13 0 13 6
17 0 17 6
21 0 21 6

2

1 0 5 10 5
0 0 10 10

0

Hint

时间限制：2000 毫秒，内存限制：1048576 kB。

国际大学生程序设计竞赛（ACM-ICPC）世界总决赛 2014。

题面翻译由 ChatGPT-4o 提供。