题意：求给出的n个矩形的面积并
题目链接：http://poj.org/problem?id=1151
思路：
终于接触扫描线了，nice~~~
1.由于坐标是浮点数，离散化（如果数据范围很大或者浮点数，离散化 ^_^）
2.如何扫着过去，求出面积呢？
看下面的图：
（直接借用的~~）
每个矩形直接转换为两条线，这两条线分别是上边和下边，对应的y1,此时对应的横坐标区间[x1,x2] 和 y2对应的横坐标区间也是[x1,x2],
同时那些线也就是y从哪里来的呢，是那些矩形的y坐标排序，这样子扫过去，只要确定了每两条线之间的宽度，那么相邻两条线的高度差*宽度也就是一个小矩形的面积了，所有的加起来也就是并的和了，
从y扫过去的时候，首先将一条边插入线段树，然后得到当前当前扫描线所在位置的覆盖到的边的总长，
第一次插入A1B1,扫描线覆盖的边长就是A1B1，再用它直接乘高度就是第一个小矩形的面积；
第二次插入的时候，扫描覆盖的边长就是A2B2,同理可得到第二个矩形的面积；
第三次插入的时候，由于已经到达第一个矩形的上边，无法进行计算，（如何判断是不是上边呢，就需要一个标记，-1）那么此时覆盖的边长也就是A3B3了，同理可得到第二个矩形的面积；
三者相加就是总面积了
注意的一点：
插入的时候也得注意，不是根据坐标计算出其离散值就当做区间直接插入，而是要将右坐标的离散值减1，这个线段树中，每个点代表一个区间
#include <iostream>
#include <stdio.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define maxn 1000
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
struct LINE{
double y,x_left,x_right;
int flag;
LINE(){}
LINE(double _y,double _x_left,double _x_right,int _f):y(_y),x_left(_x_left),x_right(_x_right),flag(_f){}
}line[maxn<<2];
int cover[maxn<<2];
double sum[maxn<<2];
double X[maxn<<2];
double x1,y1,x2,y2;
int n,t;
bool cmp(double a,double b){
if(a < b) return true;
return false;
}
bool cmp1(LINE a,LINE b){
if(a.y < b.y) return true;
return false;
}
int erfen(double res){
int left = 0 , right = t - 1, mid;
while(left <= right){
mid = (left + right )/2;
if(X[mid] == res) return mid + 1;
else if(X[mid] < res) left = mid + 1;
else right = mid - 1;
}
return -1;
}
void PushUp(int l,int r,int rt){
if(cover[rt])
sum[rt] = X[r] - X[l - 1];
else if(l == r) sum[rt] = 0;
else sum[rt] =sum[rt<<1]+ sum[rt<<1|1];
}
void update(int L,int R,int c,int l,int r,int rt){
if(L <= l && r <= R){
cover[rt] += c;
PushUp(l,r,rt);
return ;
}
int m = (l + r)/2;
if(L <= m) update(L,R,c,lson);
if(m < R) update(L,R,c,rson);
PushUp(l,r,rt);
}
int main()
{
int ncase = 1;
while(~scanf("%d",&n) && n){
t = 0;
for(int i=0;i<n;i++){
scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
line[t] = LINE(y1,x1,x2,1);
X[t++] = x1;
line[t] = LINE(y2,x1,x2,-1);
X[t++] = x2;
}
sort(X,X+t,cmp);
sort(line,line+t,cmp1);
memset(sum,0,sizeof(sum));
memset(cover,0,sizeof(cover));
double ans = 0;
for(int i = 0 ;i < t - 1;i++){
int l = erfen(line[i].x_left) ;
int r = erfen(line[i].x_right) - 1 ;
update(l , r ,line[i].flag , 1 , t , 1);
ans += (line[i + 1].y - line[i].y) * sum[1];
}
printf("Test case #%d\n",ncase++);
printf("Total explored area: %.2lf\n\n",ans);
}
return 0;
}