初见安~扫描线是一个基于线段树的算法，建议先了解下~
首先以题目为背景。
Atlantis（亚特兰蒂斯）
本题来自POJ1151，题目来自ACWing。
有几个古希腊书籍中包含了对传说中的亚特兰蒂斯岛的描述。
其中一些甚至包括岛屿部分地图。
但不幸的是，这些地图描述了亚特兰蒂斯的不同区域。
您的朋友Bill必须知道地图的总面积。
你自告奋勇写了一个计算这个总面积的程序。
输入格式
输入包含多组测试用例。
对于每组测试用例，第一行包含整数n，表示总的地图数量。
接下来n行，描绘了每张地图，每行包含四个数字x1,y1,x2,y2x1,y1,x2,y2（不一定是整数）,(x1,y1)(x1,y1)和(x2,y2)(x2,y2)分别是地图的左上角位置和右下角位置。
当输入用例n=0时，表示输入终止，该用例无需处理。
输出格式
每组测试用例输出两行。
第一行输出”Test case #k”，其中k是测试用例的编号，从1开始。
第二行输出“Total explored area：a”，其中a是总地图面积（即此测试用例中所有矩形的面积并，注意如果一片区域被多个地图包含，则在计算总面积时只计算一次），精确到小数点后两位数。
在每个测试用例后输出一个空行。
数据范围
1≤n≤1001≤n≤100,
0≤x1<x2≤1000000≤x1<x2≤100000,
0≤y1<y2≤1000000≤y1<y2≤100000
输入样例：
2
10 10 20 20
15 15 25 25.5
0
输出样例：
Test case #1
Total explored area: 180.00
这道题其实很明显，就是求n个矩形的面积并 。但是可想而知，并不是n个矩形的面积和。如下情况就很常见了（后文将以下图为例）
实际面积却只是
所以这里我们就可以用到扫描线 的思想啦！！！所以什么是扫描线呢。就是一条我们想象出来的线，会从左到右扫过整个图。我们可以发现：这条线在扫过某些位置时，线被图案覆盖的长度会变化，比如如图的位置：
但是我们同时和实际操作结合起来看，就会发现你无法判断哪个边界是会影响到大局的，所以我们操作的时候都标记一下：
是不是已经不认识这个图了所以我们认为扫描线到达红色区域就说明线被覆盖的层数发生了转变。（注意不是长度）
至于层数如何变化，也很好理解，把图精简一下就明白了：
也就是说，扫描线扫过时，这些红线对应的区间覆盖的层数都要相应的+1 或者 -1。这道题是要我们求总面积，那么我们就需要知道这些层数改变的地方对于我们的扫描线来说被覆盖的长度有没有变化，因为这些红线之间的横坐标是一定的，我们知道纵坐标就可以知道每一个长宽不一的长方形的面积，求和即可。所以接下来我们要讨论的就是——覆盖层数与覆盖长度。
已知每个矩形的对顶角坐标（x1, y1 ) 及 （x2, y2）。我们可以根据x1 和x2来存储上图红线标记信息——也就是扫描线的操作点（中间部分 线就不需要操作，我们直接计算这一段）。至于y ，我们会发现这些矩形即使有了新的出现也不一定会叠加在其他的上面，所以我们在存x的时候还得把y也放进去，现在就有3个变量捆在一起了。我们先假设用一个数组c来存储横坐标到x时覆盖的情况，那就会涉及到一个是少了一层还是多了一层的问题，所以我们还需要绑一个变量——k，并且为了方便，k存1 或者 -1，操作时直接+k即可。所以最后——这就是一个四元组（x1, y1, y2, k）（x2, y1, y2, -k）。当然，本题中k为1。
处理到这一步了，我们开始思考牵出来的c数组了——因为即使是同一横坐标x，扫描线被覆盖的情况也不会处处相等，所以需要区间维护——也就是我们的线段树啦~~~线段树维护扫描线上的区间，用cnt存这一区间被覆盖的情况，并做好延迟标记（模板不打都会超时，更何况这个），还要维护一个变量——覆盖长度。因为算面积的时候会用到，所以我们就最好开一个结构体了。长度怎么计算呢——我们这样想：离散化（后面解释）过后，如果整条扫描线都只被覆盖了一层，那就说明覆盖长度就是各个子区间的对应长度和；反之，就会少一些，也就是这个区间的原长度。（这一步代码中会比较清晰）最后提醒，在线段树维护中，如果我们还是保持着之前类似于模板的思路，即线段树上的区间的l 和 r是两个边界线，那么树上到了l == r的时候就没有意义了。所以为了我们便于继续敲模板，我们在用线段树的时候认为l 和 r 是边界区间的编号。什么意思呢——我们假设有4个高度：
那么就只有3个夹在相邻两高度之间的区间，所以我们在建树的时候就是建的区间（1，3）。而在映射过去扫描和返回len要映射的时候要注意，区间的序号和离散化后的高度的映射值是有差1的（植树问题），要注意+1 和-1.
*这里特别解释一下离散化（懂就不用看了）：因为我们的高度可以是小数，而且不知道多少位，所以在作为线段树区间的时候就可能会很不好处理，这里离散化就是把这些数转化开为我们便于计算的数，如后文的代码，就是按照高度顺序离散为了几个整数，映射后放入结构体计算，而计算完成后又需要映射回来。所以我们需要两个映射表——val和raw，正向和反向。当然离散化的方式很多，自选。
大致讲解就如上啦~下面是代码及详解（和上面对比都是略解了）——
#include<bits/stdc++.h>
using namespace std;
int n, cont = 0;
double a, b, c, d;;
map<int, double> raw;
map<double, int> val;
vector<pair<double, pair<pair<double, double>, int> > > v;//横坐标，两纵，增减
set<double> s;
struct node
{
double len;
int cnt;
}t[20020 << 2];
void init()
{
raw.clear();
val.clear();
v.clear();
s.clear();
}
void build(int p, int l, int r)//后期发现其实根本就不用build，反正本来也都是0 —_—'
{
t[p].len = t[p].cnt = 0;
if(l == r)
{
return ;
}
int mid = l + r >> 1;
build(p * 2 , l, mid);
build(p * 2 + 1, mid + 1, r);
}
void update(int p, int l, int r, int ls, int rs, int k)
{
if(ls <= l && r <= rs)
{
t[p].cnt += k;
t[p].len = t[p].cnt > 0 ? raw[r + 1] - raw[l] : t[p * 2 + 1].len + t[p * 2].len ;//层数决定长度
return ;
}
int mid = l + r >> 1;
if(ls <= mid) update(p * 2, l, mid, ls, rs, k);
if(rs > mid) update(p * 2 + 1, mid + 1, r, ls, rs, k);
t[p].len = t[p].cnt > 0 ? raw[r + 1] - raw[l] : t[p * 2].len + t[p * 2 + 1].len;
return ;//和上面一样
}
int main()
{
while(1)
{
scanf("%d", &n);
if(!n) return 0;
init();//一定要初始化
for(int i = 1; i <= n; i++)
{
scanf("%lf%lf%lf%lf", &a, &b, &c, &d);
v.push_back(make_pair(a, make_pair(make_pair(b, d), 1)));
v.push_back(make_pair(c, make_pair(make_pair(b, d), -1)));
s.insert(b);//存入涉及到的高度，set会自动排序去重
s.insert(d);
}
sort(v.begin(), v.end());
int rk = 0;
for(set<double> ::iterator it = s.begin(); it != s.end(); it++)
{
val[(*it)] = ++rk;//存储映射
raw[rk] = (*it);//反函数
}
build(1, 1, rk - 1);//以区间为边界，所以建树范围是（1， rk - 1）
double ans = 0.0, now = 0;
for(int i = 0; i < v.size(); i++)//开始扫描
{
ans += (v[i].first - now) * t[1].len;
update(1, 1, rk - 1, val[v[i].second.first.first], val[v[i].second.first.second] - 1, v[i].second.second);//看起来复杂，其实好理解
now = v[i].first;//实时更新
}
printf("Test case #%d\nTotal explored area: %.2lf\n\n", ++cont, ans);
}
}
完结撒花！！！！
迎评：）
——End——