← 返回题目

题库练习「BalticOI 2010」PCB * Printed Circuit Board

← 上一题下一题 →

A6537 | $「BalticOI 2010」PCB * Printed Circuit Board$

时间限制1s

内存限制64MB

通过 / 提交0/0

题目描述

在印刷电路板中，导电线铺设在绝缘板上。同一层中的导体一旦交叉就会产生短路，所以在一些复杂的电路中，导体板需要分成多层，由绝缘材料隔开。但是，电路板层数越多越昂贵。所以，工厂希望最小化电路板需要的层数。 我们考虑用电路板连接对边上的两个点，并最小化这种电路板的成本。 例如，考虑下图左侧所示的电路板。只需要一层电路板就可以连接 A 与 B 以及 D 与 C，方案如中间所示。但是连接 A 与 C 以及 D 与 B 就不能用一层电路板完成，如右图所示。 ![](/uploads/acgo/image/fed233a673962c91_4a03a512ebc4.png) 编写一个程序，给定 $W \times H$ 电路板上 $N$ 个导体端点的位置，计算制造电路板所需的最小层数。 可以假设导体的宽度远小于两者之间的距离。也就是说，在任何两根电线之间，总有足够的空间容纳另一根电线。

输入格式

第一行包含 $N$（$1 \le N \le 10^5$），表示电线的数量。 接下来 $N$ 行中的每一行都包含两个整数 $X_{i1}$ 和 $X_{i2}$（ $0 \le X_{ij} \le 10^6$），由空格分隔，表示第 $i$ 个导体连接点 $(X_{i1},0)$ 和 $(X_{i2},H)$。保证输入中给出的所有 $2N$ 个端点互不相同。

输出格式

输出一行一个整数，表示容纳所有电线需要的最少层数。

输入输出样例

输入 #1

2
1 1
3 3

输出 #1

输入 #2

2
1 3
3 1

输出 #2

C++ 编辑器

输入

输出