title: 题目
输入包含几个测试用例。每个测试例开始与含有可用映射的单个整数n$(1 <= N <= 100)$的线。
接下来的n行分别描述一张地图。
每条线包含四个数字
$x1; y1; x2; y2x1;y1;x2;y2$
$(0<=x1<x2<=100000;0<=y1<y2<=100000)$,不一定是整数。
值$(x1; y1)$和$(x2; y2)$是左上角的坐标。映射区域的右下角。
输入文件由包含单个0的行终止。请勿对其进行处理。
对于每个测试用例,您的程序应输出一个部分。
每个部分的第一行必须是 Testcase \#k,其中k是测试用例的编号(从1开始)。
第二个必须是Total explored area: a,其中a是总探索区(即此测试用例中所有矩形的并集面积),精确打印到小数点右边的两位数。
在每个测试用例之后输出空白行。
title: input
2
10 10 20 20
15 15 25 25.5
0
title: output
Test case #1
Total explored area: 180.00
title: 思路
**有大佬制作[视频讲解](https://www.bilibili.com/video/BV1yo4y197Zd?share_source=copy_pc)**
不过有些细节没讲, 看完可以参考我下面写的。
扫描线的算法如下:
图片来源:[POJ1151 Atlantis(线段树,扫描线,离散化,矩形面积并)_riba2534的博客-CSDN博客](https://riba2534.blog.csdn.net/article/details/76851233)
![[Pasted image 20220803221009.png]]
![[Pasted image 20220803221013.png]]
![[Pasted image 20220803221018.png]]
遇到新边时则扩大, 碰到之前的上边时就缩小
![[Pasted image 20220803221022.png]]
![[Pasted image 20220803221026.png]]
![[Pasted image 20220803221029.png]]
![[Pasted image 20220803221034.png]]
大概思路大佬那篇讲的很棒了, 我这里就配合代码讲一讲过程。
题目要求多个矩形合并起来的总面积, 以上思路中可以发现, 我们只需要存储矩形的上边和下边, 求和过程中利用线段树进行长度的变化, 从一条边扫描到另一条边时就乘上它们之间的宽度,便是这段小矩形的面积。
边的存储:
~~~ c ++
struct Seg
{
double l,r,h; // 左端点 右端点 高度
int flag; // 区分是上边还是下边
Seg(){}
Seg(double a, double b, double c, int d):l(a),r(b),h(c),flag(d){}
// 构造函数
bool operator < (const Seg &b) const
{
return h < b.h; // 根据y1 从小到大正序排序
} // 这样就从下面开始扫扫到顶端
}edge[N];
~~~
计算面积时就从低到高枚举边, `res += 当前的长度 * (下一条边的高度 - 当前边的高度)`
**如何求当前的长度呢?**
我们需要知道当前有哪些区间是正在被使用的, 可以用一个数组当做x轴, 每次查询就遍历一次数轴来统计当前长度, 这种方法首先很慢, 其次这里的数是包含小数, 不能只用下标来保存。
小数很好处理, 我们可以将所有点的x坐标进行排序, 然后利用在排序后的位置信息来遍历整个数轴。这种操作就是离散化。
既然是区间问题我们就可以使用线段树来解决:
每个节点储存当前区间的已被使用长度(len), 当前区间是否完全被使用(cnt)
需要用到的操作是区间更新和树根查询(t[1]):
区间更新正常来说是需要lazy懒标记来优化时间, 这里我们并不需要, 因为用到一个区间时并不会去关心它的子区间, 如果一个区间被完全使用, 那么它就可以被当做一个叶子区间(最小区间),不需要再往下划分。
所以只需要一个 pushup 操作来更新父节点:
~~~ c ++
void pushup(int l, int r, int u)
{
if(t[u].cnt) // 如果当前区间被完全使用
t[u].len = x[r + 1] - x[l]; // 加上当前区间的长度 右端点-左端点
else if(l == r) // 若左右端点相同则长度为0
t[u].len = 0;
else // 未被完全使用的话就是子区间被使用的长度之和
t[u].len = t[u << 1].len + t[u << 1 | 1].len;
}
~~~
**为什么用 x[r + 1] 而不是 x[r]?**
线段树存的并不是当前 [l,r] 的长度, 而是 [l, r + 1] 的长度, 避免出现 [3,3] 这种即是点又是线段的情况出现, 保证每个节点都存的是一条线段, 也方便判断当前区间是否为点(l == r)。
需要构建一个树嘛?不需要, 默认值就是0,我们只用实现update方法即可:
~~~ c ++
void update(int L,int R, int l, int r, int u, int val) // LR是目标区间,lr是线段树区间
{
if(L <= l && R >= r) // 若当前节点在目标区间内
{
t[u].cnt += val; // val为1则加上该边, 为-1则减去该边
pushup(l,r,u); // 直接更新, 可以不用这个, 只写 t[u].len = x[r + 1] - x[l] 不过效果一样
return;
}
int mid = l + r >> 1;
if(L <= mid)
update(L,R,l,mid,u << 1, val);
if(R > mid)
update(L,R,mid+1,r,u<< 1 | 1, val);
pushup(u);
}
~~~
main函数里面就看下面代码的注释吧。
这题是相当难的一道线段树, 不仅仅是用到了扫描线扩展知识, 重要的是把每个节点的值都看成线段和每个节点都有含义这两个思想, 对于深刻理解线段树很有帮助(编的)
不过写出来之后确实感觉很棒, 各位加油!
参考博客:
[【hdu1542】线段树求矩形面积并 - 拦路雨偏似雪花 - 博客园 (cnblogs.com)](https://www.cnblogs.com/KonjakJuruo/p/6024266.html)
[POJ1151 Atlantis(线段树,扫描线,离散化,矩形面积并)_riba2534的博客-CSDN博客](https://riba2534.blog.csdn.net/article/details/76851233)
title:代码
~~~ c ++
#include <iostream>
#include <iomanip>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 220;
struct Seg
{
double l, r, h;
int flag;
Seg() {}
Seg(double l, double r, double h, int flag) : l(l), r(r), h(h), flag(flag) {}
bool operator<(const Seg &b) const
{
return h < b.h;
}
} edge[N];
struct Node
{
int cnt; // 该区间是否被完全使用上
double len;
} t[N << 2];
double x[N]; // 用来离散化储存坐标x
void pushup(int l, int r, int u)
{
if (t[u].cnt)
t[u].len = x[r + 1] - x[l];
else if (l == r) // 该区间未全被使用
t[u].len = 0;
else // 当前区间没占满, 为两个子节点区间长度之和
t[u].len = t[u << 1].len + t[u << 1 | 1].len;
}
void update(int L, int R, int l, int r, int u, int val)
{
if (L <= l && R >= r)
{
t[u].cnt += val;
pushup(l, r, u);
return;
}
int mid = l + r >> 1;
if (L <= mid)
update(L, R, l, mid, u << 1, val);
if (R > mid)
update(L, R, mid + 1, r, u << 1 | 1, val);
pushup(l, r, u);
}
int main()
{
cin.tie(0)->sync_with_stdio(false); // 快读
cout << fixed << setprecision(2); // 保留两位小数 iomanip
int n, kase = 0;
while (cin >> n && n)
{
memset(t, 0, sizeof t);
int cnt = 0; // 用于存放数据的下标
for (int i = 0; i < n; i++)
{
double a, b, c, d;
cin >> a >> b >> c >> d;
x[cnt] = a, edge[cnt++] = Seg(a, c, b, 1); // 上边
x[cnt] = c, edge[cnt++] = Seg(a, c, d, -1); // 下边
}
sort(x, x + cnt);
/*
for (int i = 0; i < cnt; i++)
cout << x[i] << " ";
cout << endl;
*/
sort(edge, edge + cnt);
int m = unique(x, x + cnt) - x; // 不重复部分的尾部
double res = 0;
for (int i = 0; i < cnt; i++)
{
int l = lower_bound(x, x + m, edge[i].l) - x; // 二分查找
int r = lower_bound(x, x + m, edge[i].r) - x - 1;
//cout << i << ": " << l << " " << r << endl;
update(l, r, 0, m, 1, edge[i].flag); // 加边 或者 减边
res += t[1].len * (edge[i + 1].h - edge[i].h); // 长 * (宽)
//cout << "len : " << t[1].len << endl;
}
cout << "Test case #" << ++kase << "\nTotal explored area: " << res << "\n\n";
}
}
~~~