线段树 扫描线 浮点离散化 线段树存线段 区间查询 区间修改 T5 247. 亚特兰蒂斯 - AcWing题库 有几个古希腊书籍中包含了对传说中的亚特兰蒂斯岛的描述。
其中一些甚至包括岛屿部分地图。
但不幸的是，这些地图描述了亚特兰蒂斯的不同区域。
您的朋友 Bill 必须知道地图的总面积。
你自告奋勇写了一个计算这个总面积的程序。
输入格式
输入包含多组测试用例。
对于每组测试用例，第一行包含整数 ，表示总的地图数量。
接下来 行，描绘了每张地图，每行包含四个数字 （不一定是整数）， 和 分别是地图的左上角位置和右下角位置。
注意，坐标轴 轴从上向下延伸， 轴从左向右延伸。
当输入用例 时，表示输入终止，该用例无需处理。
输出格式
每组测试用例输出两行。
第一行输出 Test case #k，其中 是测试用例的编号，从 开始。
第二行输出 Total explored area: a，其中 是总地图面积（即此测试用例中所有矩形的面积并，注意如果一片区域被多个地图包含，则在计算总面积时只计算一次），精确到小数点后两位数。
在每个测试用例后输出一个空行。
数据范围
,
,
注意，本题 的范围上限加强至 。
输入样例：
2
10 10 20 20
15 15 25 25.5
0
输出样例：
Test case #1
Total explored area: 180.00
样例解释
样例所示地图覆盖区域如下图所示，两个矩形区域所覆盖的总面积，即为样例的解。
思路
求矩形并集面积和, 普遍的解法是用线段树维护一个线段, 沿y轴从低到高扫一遍, 类似于积分求面积一样, 把其分为一块一块小矩形：
在求面积时 。
可以边扫边计算已经扫过的面积。这样可以用 的复杂度解决这道题。
需要实现能快速求得当前x轴上的线段长度, 定义一个 cnt 记录当前区间是否被用到, 扫到矩形左侧边时, 把对应区间cnt +1, 扫到右侧边时, 再把对应区间cnt -1, 而查询时只累加cnt > 0 的区间即可。
线段树需要做的操作有：
- 区间修改
- 区间查询 但本题比较特殊, 查询时只会查询 根节点 即 , 修改也是成对出现, 故不需要用到 lazy 操作, 只修改高层区间就行。
线段树节点中维护的也不是点集, 而是一个个的线段, 对于这个y轴坐标序列：, 我们维护的是 , 这三个点在线段树的下标为 0, 1, 2。因此, 当我们要访问 区间时, 对应在线段树中的节点下标区间为 。
本题中的点坐标是浮点数, 故还需要一个离散化操作, 以及将线段坐标转化为离散化后下标的find函数。
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#define lson t[u].l, mid, u << 1
#define rson mid + 1, t[u].r, u << 1 | 1
using namespace std;
const int N = 1e4 + 10;
struct Seg {
double x, y1, y2;
int cnt;
bool operator < (const Seg &w) const {
return x < w.x;
}
}seg[N*2];
int n,m, cnt;
struct Node {
int l, r;
double len;
int cnt;
}t[N*8];
vector<double> ys;
int find(double x)
{
return lower_bound(ys.begin(), ys.end(), x) - ys.begin();
}
void pushup(int u)
{
if(t[u].cnt)
t[u].len = ys[t[u].r + 1] - ys[t[u].l];
else if(t[u].r != t[u].l)
t[u].len = t[u << 1].len + t[u << 1 | 1].len;
else
t[u].len = 0;
}
void build(int l ,int r ,int u = 1)
{
t[u] = {l,r, 0,0};
if(l != r)
{
int mid = l + r >> 1;
build(l, mid, u << 1);
build(mid + 1, r, u << 1 | 1);
}
}
void update(int L, int R, int val, int u = 1)
{
if(L <= t[u].l && t[u].r <= R)
{
t[u].cnt += val;
pushup(u);
return;
}
int mid = t[u].l + t[u].r >> 1;
if(L <= mid) update(L, R, val, u << 1);
if(R > mid) update(L, R, val, u << 1 | 1);
pushup(u);
}
int main()
{
int T = 1;
while(cin >> n,n)
{
memset(t, 0, sizeof t);
ys.clear();
cnt = 0;
for(int i = 1; i <= n;i ++)
{
double x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
seg[cnt++] = {x1, y1, y2, 1};
seg[cnt++] = {x2, y1, y2, -1};
ys.push_back(y1), ys.push_back(y2);
}
sort(seg, seg + cnt);
sort(ys.begin(), ys.end());
ys.erase(unique(ys.begin(), ys.end()), ys.end());
// cout << ys.size() - 2 << endl;
build(0,ys.size() - 2, 1);
double res = 0;
for(int i = 0; i < cnt; i++)
{
if(i) res += t[1].len * (seg[i].x - seg[i - 1].x);
update(find(seg[i].y1), find(seg[i].y2) - 1, seg[i].cnt);
}
printf("Test case #%d\n", T++);
printf("Total explored area: %.2lf\n\n", res);
}
return 0;
}