hdu 1542 Atlantis (线段树+扫描线求矩形面积并，模板题)
题意：
求n(100)个矩形的面积并。
思路：
扫描线+线段树
题目是2000年中欧区域赛的题目，虽然年代久远，但是有好几个点还是很值得学习的。
首先是离散化的适用范围:
之前比较常用的是将比较大的整数值离散化，常常是因为数值太大无法作为下标。
那么其实，浮点数有的时候也需要进行离散化，比如作为数组的下标，比如用来枚举。
做法上是和将较大的整数值离散化没有区别，因为遇到的题目不多，所以特意记录一下。
第二点是扫描线的思想：
其实扫描线的思想很早就接触过，noip2011的时候，tyvj上有一道类似的题目，不过是一唯的，当时印象深刻的是@Ocean 兄的那个比喻：
一段公路上右很多区间要收不同的费用，区间的开始给一个标记，表示该段区间对答案有贡献，区间的结束拿走该标记，表示该段区间对答案的贡献结束。
这就是扫描线的思想。
第三个是处理线段覆盖问题的一般做法：
通常线段树的节点处理的都是点，处理线段的时候就会比较麻烦。
另外很重要的一点就是， 线段树都是维护一个点集， 但是对于边的问题就会变得很麻烦， 我们可以按照区间左端点建立线段树， 那么一个点表示的就不是点了， 而是起点在这个点的一个线段。 这**样的话， 右区间就要相应的-1， 例如更新区间[1, 4]， 就相当于更新标号为[1, 3]的线段。**这也是处理线段覆盖问题的通用方法。
对于上面引用中提到的例子中“更新[1,4]，就相当于更新标号为[1,3]的线段”，是因为标号为1的节点代表区间[1,2]，标号为2的节点代表区间[2,3],标号为3的节点代表期间[3,4]
接下来具体讨论这道题目的做法：
将矩形按平行x轴方形构建扫描线（只是思想，不用实际构造），
每个矩形2条平行x轴的边分类{上边，下边}2类，如果我们从下往上“扫描”线，那么[下边]就表示了对答案贡献的开始，[下边]就表示了对答案贡献的结束。
* 扫描线扫描的过程（建议配合代码模拟）
**以下图转载自@kk303的博客**
初始状态
扫到最下边的线, 点1→3更新为1
扫到第二根线, 此时S=lcnt!=0∗h两根线之间, 得到绿色的面积, 加到答案中去, 随后更新计数
同上, 将黄色的面积加到答案中去
同上, 将灰色的面积加到答案中去
同上, 将紫色的面积加到答案中去
/* ***********************************************
Author :111qqz
Created Time :2017年09月27日 星期三 16时37分39秒
File Name :1542.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define PB push_back
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=205;
int n;
double X[N]; //存储所有x坐标，用来离散化。
//扫描线
struct Seg
{
double l,r,h;
//表示扫面线的起点，终点，所在的高度(y坐标）
int d;//1或者-1，表示扫描线对面积是正向影响还是负向影响
Seg(){}
Seg(double l,double r,double h,int d):l(l),r(r),h(h),d(d){}
bool operator < (const Seg &rhs)const
{
return h<rhs.h;
}
//从下向上处理扫描线。
}seg[N];
struct Tree
{
int cnt;
double len;
}tree[N<<2];
void PushUp(int l,int r,int rt)
{
/*由于线段树的节点表示的其实是长度为1的区间
* 因此线段树的区间[l,r]，对应的点的端点是l,r+1
*/
if (tree[rt].cnt) tree[rt].len = X[r+1]-X[l]; //当前区间已经完全被线段覆盖
else if (l==r) tree[rt].len=0; //是叶子节点而且没有被覆盖。
else tree[rt].len = tree[rt<<1].len + tree[rt<<1|1].len; //没有完全被覆盖，从其子区间获得信息。
}
void update( int L,int R,int v,int l,int r,int rt)
{
if (L<=l && r<=R)
{
tree[rt].cnt+=v;
PushUp(l,r,rt);
return;
}
int m = (l+r)>>1;
if (L<=m) update(L,R,v,lson);
if (R>=m+1) update(L,R,v,rson);
PushUp(l,r,rt);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("./in.txt","r",stdin);
#endif
int cas = 0;
while (~scanf("%d",&n)&&n)
{
ms(tree,0);
for ( int i = 1 ; i <= n ; i++)
{
double x1,y1,x2,y2;
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
seg[i] = Seg(x1,x2,y1,1);
seg[i+n]= Seg(x1,x2,y2,-1);
X[i] = x1;
X[i+n] = x2;
}
n<<=1;
sort(X+1,X+n+1);
int m = unique(X+1,X+1+n)-X-1;
sort(seg+1,seg+n+1);
double ans = 0;
for ( int i = 1 ; i < n ; i++)
{
int l = lower_bound(X+1,X+1+m,seg[i].l)-X;
int r = lower_bound(X+1,X+1+m,seg[i].r)-X;
if (l<r)
update(l,r-1,seg[i].d,1,m,1);
ans += tree[1].len * (seg[i+1].h-seg[i].h);
}
printf("Test case #%d\nTotal explored area: %.2f\n\n",++cas,ans);
}
#ifndef ONLINE_JUDGE
fclose(stdin);
#endif
return 0;
}