#SLT02D. 2026年S组模拟赛10连测第2场-T4 地块拼合
2026年S组模拟赛10连测第2场-T4 地块拼合
| 项目 | 内容 |
|---|---|
| 输入文件名 | blocks.in |
| 输出文件名 | blocks.out |
| 可执行文件名 | blocks |
| 每个测试点时限 | 1.5 秒 |
| 内存限制 | 512 MiB |
| 测试点数目 | 20 |
| 是否等分 | 是 |
结果比较方式为全文比较(过滤行末空格及文末换行)。
题目描述
市规划局的测绘科刚刚完成一片新区的外业测量,成果表上登记着 个矩形地块。每个矩形的边均平行于坐标轴,第 个地块由它的左下角 与右上角 唯一确定,边界线本身计入地块范围。
内业归档前需要把地块划分成若干连通片。测绘规程对"相连"的认定如下:两个地块相连,当且仅当它们存在面积重叠,或者拥有一段公共的边界段——即两条边界线重合的部分是一段长度大于 的线段。需要特别执行的是,仅在孤立的点上相接不算相连:两块地块即使角对角顶在一起,或一方的角恰好顶在另一方的边界线上,只要公共部分只是一个点,就不能认定为相连。
相连关系具有传递性:若地块 与地块 相连,地块 与地块 相连,则 、、 划入同一片。按此规程,全部地块被唯一地划分成若干连通片,每片内部任意两块都可以通过若干次相连关系衔接起来,不同片之间不存在任何相连关系。
请你根据成果表统计:这片新区的地块一共被划分成多少个连通片。
输入格式
从文件 blocks.in 中读入数据。
- 第一行一个整数 ,表示地块数量;
- 接下来 行,每行四个整数 ,依次表示第 个地块左下角与右上角的坐标。
输出格式
输出到文件 blocks.out 中。
输出一行一个整数,表示连通片的数量。
样例
4
0 0 3 2
2 1 5 3
5 0 7 2
0 5 2 7
2
样例 1 解释
第 块与第 块存在面积重叠,认定相连。第 块的右侧边界与第 块的左侧边界在纵坐标 到 之间重合,这是一段长度大于 的公共边界段,两者相连。于是前三块划入同一片。第 块与前三块均无公共部分,单独成片。共 片。
3
0 0 2 2
2 2 4 4
6 0 8 1
3
样例 2 解释
第 块的右上角 恰好是第 块的左下角,两者的公共部分只有这一个点。按规程,仅在孤立的点上相接不算相连,两块各自单独成片。第 块与其余两块均无公共部分。三块各自成片,共 片。
3
0 0 2 3
2 1 4 2
3 2 5 4
1
样例 3 解释
第 1 块的右侧边界与第 2 块的左侧边界在纵坐标 到 之间重合,重合部分长度为 ;第 2 块的上侧边界与第 3 块的下侧边界在横坐标 到 之间重合,重合部分长度同样为 。两段重合部分长度均大于 ,三块依次衔接成一整片,共 片。
数据范围
对于所有测试数据,保证:
- ;
- ,。
各测试点的约束如下:
| 测试点 | 坐标范围 | 特殊性质 | |
|---|---|---|---|
| 无 | |||
- ID
- 3776
- 类型
- 传统题
- Time Limit
- 1500ms
- Memory Limit
- 512MiB
- 上传者