← 返回题目列表

AtCoder · icpc2013summer_day4_d

D. 移除魔法瓷砖

中文机器翻译题面 查看原题

问题陈述

Ayimok 是一名巫师。

他的日常任务是将魔法方块排成一行,然后施展魔法咒语。

魔法方块及其排列遵循以下规则:

  • 每个魔法图块的形状都是梯形,高度为 1。

  • 一些魔法图块可能会与其他魔法图块重叠。

  • 魔法方块排列在 2D 坐标系上。

  • 魔法方块的上边缘位于水平线上,其 y 坐标为 1。

  • 魔法方块的下边缘位于水平线上,其 y 坐标为 0。

他必须在施展完魔法咒语后将这些魔法瓷砖移走。 有一天,他发现移除一些魔法瓷砖是如此烦人,因此他决定简化其过程。

现在,他已经学会了“磁化法术”,可以有效地去除魔法瓷砖。 该法术会立即移除一组魔法瓷砖。该组中的任意两块魔法图块必须彼此重叠。

例如,在图1中,他可以对所有三个魔法方块施展磁化法术,将它们一次性移除,因为它们都相互重叠。 (请注意,为了更容易理解,故意更改了魔法图块的高度。)

图1:一组可以立即移除的魔法方块

然而,在图2中,他不能同时对所有三个魔法图块施放磁化法术,因为图块1和图块3不重叠。

图 2:无法立即移除的一组魔法方块

他想用最少数量的磁化法术移除所有魔法方块,因为施展该法术需要消耗大量的魔力。

让我们考虑图 3 的情况。他可以通过施放磁化法术三次来消除所有魔法方块;第一个咒语用于图块 1 和 2,第二个咒语用于图块 3 和 4,第三个咒语用于图块 5 和 6。

图 3:移除所有魔法方块的一种方法(不是施放法术的最低数量)

实际上,他只需施放两次磁化法术就可以消除所有的魔法方块;第一个咒语用于图块 1、2 和 3,第二个咒语用于图块 4、5 和 6。 这是消除所有魔法方块所需的最少法术数量。

图4:移除所有魔法方块的最佳方式(施展最少法术数量)

给定一组魔法方块,你的任务是创建一个程序,输出最少数量的施放磁化法术,以消除所有这些魔法方块。

可能有一块魔法图块不与其他图块重叠,但是,他仍然需要施展磁化法术来将其移除。


输入

输入遵循以下格式:

N
xLower_{11} xLower_{12} xUpper_{11} xUpper_{12}
xLower_{21} xLower_{22} xUpper_{21} xUpper_{22}
xLower_{31} xLower_{32} xUpper_{31} xUpper_{32}
:
:
xLower_{N1} xLower_{N2} xUpper_{N1} xUpper_{N2}

第一行包含一个整数 N,表示魔法图块的数量。

然后, N 行包含魔法图块的信息。

的 树的 (i+1)第行包含四个整数 xLower_{i1}, xLower_{i2}, xUpper_{i1},和 xUpper_{i2},这意味着 i第一个魔法图块的角点位于 (xLower_{i1}, 0), (xLower_{i2}, 0), (xUpper_{i1}, 1), (xUpper_{i2}, 1).

你可以假设没有两个魔法图块会共享它们的角点。 也就是说,所有 xLower_{ij} 是不同的,并且所有 xUpper_{ij} 也不同。 输入遵循以下约束:

  • 1 \leq N \leq 10^5

  • 1 \leq xLower_{i1} < xLower_{i2} \leq 10^9

  • 1 \leq xUpper_{i1} < xUpper_{i2} \leq 10^9

  • 全部 xLower_{ij} 是不同的。

  • 全部 xUpper_{ij} 是不同的。

输出

你的程序必须输出施展磁化法术所需的最小数量,以移除所有魔法方块。


示例输入 1

3
26 29 9 12
6 10 15 16
8 17 18 19

样本输入 1 的输出

1

示例输入 2

3
2 10 1 11
5 18 9 16
12 19 15 20

样本输入 2 的输出

2

示例输入 3

6
2 8 1 14
6 16 3 10
3 20 11 13
17 28 18 21
22 29 25 31
23 24 33 34

样本输入 3 的输出

2