#SLT02D. 2026年S组模拟赛10连测第2场-T4 地块拼合

2026年S组模拟赛10连测第2场-T4 地块拼合

项目 内容
输入文件名 blocks.in
输出文件名 blocks.out
可执行文件名 blocks
每个测试点时限 1.5 秒
内存限制 512 MiB
测试点数目 20
是否等分 是

结果比较方式为全文比较(过滤行末空格及文末换行)。

题目描述

市规划局的测绘科刚刚完成一片新区的外业测量,成果表上登记着 nn 个矩形地块。每个矩形的边均平行于坐标轴,第 ii 个地块由它的左下角 (x1,i,y1,i)(x_{1,i}, y_{1,i}) 与右上角 (x2,i,y2,i)(x_{2,i}, y_{2,i}) 唯一确定,边界线本身计入地块范围。

内业归档前需要把地块划分成若干连通片。测绘规程对"相连"的认定如下:两个地块相连,当且仅当它们存在面积重叠,或者拥有一段公共的边界段——即两条边界线重合的部分是一段长度大于 00 的线段。需要特别执行的是,仅在孤立的点上相接不算相连:两块地块即使角对角顶在一起,或一方的角恰好顶在另一方的边界线上,只要公共部分只是一个点,就不能认定为相连。

相连关系具有传递性:若地块 AA 与地块 BB 相连,地块 BB 与地块 CC 相连,则 AA、BB、CC 划入同一片。按此规程,全部地块被唯一地划分成若干连通片,每片内部任意两块都可以通过若干次相连关系衔接起来,不同片之间不存在任何相连关系。

请你根据成果表统计:这片新区的地块一共被划分成多少个连通片。

输入格式

从文件 blocks.in 中读入数据。

  • 第一行一个整数 nn,表示地块数量;
  • 接下来 nn 行,每行四个整数 x1,i,y1,i,x2,i,y2,ix_{1,i}, y_{1,i}, x_{2,i}, y_{2,i},依次表示第 ii 个地块左下角与右上角的坐标。

输出格式

输出到文件 blocks.out 中。

输出一行一个整数,表示连通片的数量。

样例

4
0 0 3 2
2 1 5 3
5 0 7 2
0 5 2 7
2

样例 1 解释

第 11 块与第 22 块存在面积重叠,认定相连。第 22 块的右侧边界与第 33 块的左侧边界在纵坐标 11 到 22 之间重合,这是一段长度大于 00 的公共边界段,两者相连。于是前三块划入同一片。第 44 块与前三块均无公共部分,单独成片。共 22 片。

3
0 0 2 2
2 2 4 4
6 0 8 1
3

样例 2 解释

第 11 块的右上角 (2,2)(2,2) 恰好是第 22 块的左下角,两者的公共部分只有这一个点。按规程,仅在孤立的点上相接不算相连,两块各自单独成片。第 33 块与其余两块均无公共部分。三块各自成片,共 33 片。

3
0 0 2 3
2 1 4 2
3 2 5 4
1

样例 3 解释

第 1 块的右侧边界与第 2 块的左侧边界在纵坐标 11 到 22 之间重合,重合部分长度为 11;第 2 块的上侧边界与第 3 块的下侧边界在横坐标 33 到 44 之间重合,重合部分长度同样为 11。两段重合部分长度均大于 00,三块依次衔接成一整片,共 11 片。

数据范围

对于所有测试数据,保证:

  • 1≤n≤1051 \le n \le 10^5;
  • 0≤x1,i<x2,i≤1090 \le x_{1,i} < x_{2,i} \le 10^9,0≤y1,i<y2,i≤1090 \le y_{1,i} < y_{2,i} \le 10^9。

各测试点的约束如下:

测试点 nn 坐标范围 特殊性质
1∼31\sim3 ≤15\le 15 ≤20\le 20 无
4∼84\sim8 ≤2000\le 2000 ≤109\le 10^9
9∼129\sim12 ≤105\le 10^5 ≤1000\le 1000
13∼2013\sim20 ≤109\le 10^9
难度 未评定
通过率 —
尝试 0
通过 0
ID
3776
类型
传统题
Time Limit
1500ms
Memory Limit
512MiB
上传者