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
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define PB push_back
14#define fst first
15#define sec second
16#define lson l,m,rt<<1
17#define rson m+1,r,rt<<1|1
18#define ms(a,x) memset(a,x,sizeof(a))
19typedef long long LL;
20#define pi pair < int ,int >
21#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=205;
7int n;
1double X[N]; //存储所有x坐标，用来离散化。
2//扫描线
3struct Seg
4{
5 double l,r,h;
6 //表示扫面线的起点，终点，所在的高度(y坐标）
7 int d;//1或者-1，表示扫描线对面积是正向影响还是负向影响
8 Seg(){}
9 Seg(double l,double r,double h,int d):l(l),r(r),h(h),d(d){}
10 bool operator < (const Seg &rhs)const
11 {
12 return h<rhs.h;
13 }
14 //从下向上处理扫描线。
15}seg[N];
16struct Tree
17{
18 int cnt;
19 double len;
20}tree[N<<2];
21void PushUp(int l,int r,int rt)
22{
23 /*由于线段树的节点表示的其实是长度为1的区间
24 * 因此线段树的区间[l,r]，对应的点的端点是l,r+1
25 */
26 if (tree[rt].cnt) tree[rt].len = X[r+1]-X[l]; //当前区间已经完全被线段覆盖
27 else if (l==r) tree[rt].len=0; //是叶子节点而且没有被覆盖。
28 else tree[rt].len = tree[rt<<1].len + tree[rt<<1|1].len; //没有完全被覆盖，从其子区间获得信息。
29}
1void update( int L,int R,int v,int l,int r,int rt)
2{
3 if (L<=l && r<=R)
4 {
5 tree[rt].cnt+=v;
6 PushUp(l,r,rt);
7 return;
8 }
9 int m = (l+r)>>1;
10 if (L<=m) update(L,R,v,lson);
11 if (R>=m+1) update(L,R,v,rson);
12 PushUp(l,r,rt);
13}
14int main()
15{
16 #ifndef ONLINE_JUDGE
17 freopen("./in.txt","r",stdin);
18 #endif
19 int cas = 0;
20 while (~scanf("%d",&n)&&n)
21 {
22 ms(tree,0);
23 for ( int i = 1 ; i <= n ; i++)
24 {
25 double x1,y1,x2,y2;
26 scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
27 seg[i] = Seg(x1,x2,y1,1);
28 seg[i+n]= Seg(x1,x2,y2,-1);
29 X[i] = x1;
30 X[i+n] = x2;
31 }
32 n<<=1;
33 sort(X+1,X+n+1);
34 int m = unique(X+1,X+1+n)-X-1;
1 sort(seg+1,seg+n+1);
2 double ans = 0;
3 for ( int i = 1 ; i < n ; i++)
4 {
5 int l = lower_bound(X+1,X+1+m,seg[i].l)-X;
6 int r = lower_bound(X+1,X+1+m,seg[i].r)-X;
7 if (l<r)
8 update(l,r-1,seg[i].d,1,m,1);
9 ans += tree[1].len * (seg[i+1].h-seg[i].h);
10 }
11 printf("Test case #%d\nTotal explored area: %.2f\n\n",++cas,ans);
}
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}