XLII 保加利亚国家信息学奥林匹克竞赛

地区赛，2026 年 2 月 14 日 D 组（6 年级）

---

题目 D3：矩形（RECTANGLES）

时间限制： 0.1 秒 内存限制： 3 MB 作者： Emil Kelevedzhiev（埃米尔·凯莱韦季耶夫）

---

题目背景

在平面直角坐标系中，给定 (n) 个边与坐标轴平行的矩形。 我们希望用颜料​给所有矩形的边涂色​。

规定：

• 给一段长度为 1 的线段涂色，需要 1 单位 的颜料。

请你编写程序 rect，计算：

1. ​这 (n) 个矩形周长的总和​；
2. ​实际需要使用的最少颜料数量​（如果多条边重合，那么​重合部分只涂一次​）。

---

输入格式

标准输入的第一行是一个整数：

n

接下来有 (n) 行，每行包含 ​4 个整数​，表示一个矩形的两个角的坐标：

x1 y1 x2 y2

其中：

• ((x1, y1)) 是左下角坐标
• ((x2, y2)) 是右上角坐标
• 各数之间用空格分隔

---

输出格式

标准输出应包含 ​两行​：

1. 第一行：输出一个整数 —— ​所有矩形周长之和​；
2. 第二行：输出一个整数 —— ​涂色所需的最少颜料单位数​（即所有边的​并集长度​）。

---

输入数据限制

• $(1 \le n \le 20000)$
• 对每个矩形：
  • $(0 \le x_1 < x_2 \le 1000)$
  • $(0 \le y_1 < y_2 \le 1000)$

---

评分说明

• 如果**第一行（周长总和）**输出正确，可获得该测试 33% 的分数；
• 如果**第二行（最少颜料用量）**输出正确，可获得该测试 67% 的分数；
• 在 77% 的测试中：$(n \le 5000)$

---

样例

样例 1

输入：

2
0 0 1 2
1 0 2 1

输出：

10
9

说明： 第一个矩形的周长是 6，第二个矩形的周长是 4，总和为 ​10​，因此第一行输出 10。 这两个矩形的边界​有一段长度为 1 的公共线段​。在涂色时，这一段​只需要涂一次​， 所以实际需要的颜料是 (10 - 1 = 9)，第二行输出 ​9​。

---

样例 2

输入：

2
1 1 3 3
1 1 3 3

输出：

16
8

---

样例 3

输入：

3
0 0 1 2
1 0 2 1
0 0 2 2

输出：

18
11

---

题目要点理解（中文提示）

• 第一问：
  • 直接把每个矩形的周长$(2 \times ((x_2-x_1) + (y_2-y_1)))$加起来即可。
• 第二问（关键）：
  • 要求的是​所有矩形边界的并集长度​；
  • 如果多条边​重合或部分重合​，重合的部分​只能算一次​；
  • 可以把所有水平边和竖直边分别处理，用扫描线 / 区间合并的方法计算总长度。

这道题本质上是：

​**求一堆轴对齐线段集合的并集总长度（分横向和纵向两类）**​。