P15885 [ICPC 2026 NAC] Kindergarten Revisited
题目描述
在幼儿园里，最耗时的活动之一就是用安全剪刀从一张纸上剪下各种形状。
让我们来看这个任务的简化模型：你开始时有一张无限大的纸，纸上画有 $N$ 个互不相交的轴对齐矩形，而剪裁工具是无限长的直线。
一条剪裁线 **不得** 划伤任何矩形：即它不能穿过任何矩形内部的任意点。（剪裁线 **恰好** 沿着矩形边缘或通过矩形角点是允许的。）
当你剪裁一张纸时，纸张会分成两个不同的部分，你可以继续独立地对每个部分进行剪裁（对一个部分的后续剪裁 **不会** 影响其他部分）。
你的目标是进行一系列剪裁，使得最终每个矩形都单独位于一张纸上（因为在那之后，就可以很容易地精确剪出每个矩形）。
请确定完成这种分离所需的最少剪裁次数（剪裁线不一定与坐标轴平行）。如果任务不可能完成，则输出 `impossible`。
输入格式
输入的第一行包含一个整数 $N$ $(1 \leq N \leq 100)$，表示矩形的数量。
接下来的 $N$ 行，每行描述一个矩形。每行包含四个空格分隔的整数 $x_1$、$y_1$、$x_2$ 和 $y_2$ $(|x_1|, |y_1|, |x_2|, |y_2| \leq 10^9,\ x_1 < x_2,\ y_1 < y_2)$，其中 $(x_1, y_1)$ 是矩形的左下角，$(x_2, y_2)$ 是矩形的右上角。
保证所有矩形互不相交：任意两个矩形没有公共点，包括它们的边或角。
输出格式
输出分离所有矩形所需的最少剪裁次数。（一旦矩形被分离， **不要** 计入额外剪裁空白纸张边缘所需的次数。）如果任务不可能完成，则输出 `impossible`。
说明/提示
### 样例输入 1 解释
下图中展示了分离矩形的一种可能剪裁序列的前两次剪裁。第一次剪裁用红色表示，第二次用蓝色表示。
注意，在红色剪裁之前，蓝色剪裁是无效的，因为它会划伤右侧的矩形。
:::align{center}
:::
翻译由 DeepSeek V3.2 完成