POJ-1151 扫描线&离散化&线段树&矩形面积求并

初次接触扫描线的第一个题目，理解扫描线的后，我感觉扫描线和平时人脑解决很多矩形堆叠在一起所占的面积的思维是一样的，如果是两个图形叠在一起，可以分别求两个图形的面积再减去重合部分的面积；但是一旦堆叠在一起的图形很多，求解起来就非常麻烦，n^2级别的复杂度，这种方法就不好使了；

扫描线法充分利用了线段树区间修改的优势，将堆叠再一起的图形分成块后，区间修改并查询这块图形的总长度，因为每块图形的总高度都相同，所以直接将长度和高相乘就可以得到这块图形的面积了，每块加起来就是总面积了。

从大佬那里看到的图感觉很好理解扫描线

红色的线代表扫描线，总长度指的是现在存在于这条扫描线上的线段的总长度，用线段树维护；

不同的色块就是分成的每块图形，每块图形的高可以由输入的坐标的得出。

题意：给你n个边平行于坐标轴的矩阵(任意两个矩阵可能重叠),让要你求这些矩阵的总面积。

解题过程：题目的表述应该是有点问题，每个矩形给了左下角和右上角的坐标。扫描线之前先要对横坐标离散化一下（纵坐标也可以）如果不离散的话就相当于用最大的纵坐标来建树，非常浪费空间和更新的时间，也很可能爆内存；所以要进行离散化，我们先对所有横坐标进行排序，然后去重，这样得出的端点按照顺数得出的下标（这里就是将一段很大的区间映射到一个小区间内）就可以作为线；段树的最下层子节点，然后通过二分找值就可以了找到两个横坐标对应的区间进行区间更新。

这里的区间更新其实就是扫描线扫描的过程。

#include<iostream>
#include<cstring>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <stack>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
struct node{
	double l,r,h;
	int f;
	node() {}
	bool operator < (const node &cmp) const
	{
		return h<cmp.h;
	}
}e[250];
struct tr{
	int l,r,cnt;
	double len;
}tree[4*250];
double x[250];
void build(int i,int l,int r){
	tree[i].l=l;tree[i].r=r;
	tree[i].cnt=tree[i].len=0;
	if(l==r){
		return;
	}
	build(i<<1,l,(int)floor((r+l)/2.0));
	build((i<<1)+1,(int)floor((r+l)/2.0)+1,r);
}
void pushdown(int i){
	if(tree[i].cnt)
		tree[i].len=x[tree[i].r+1]-x[tree[i].l];
	else if(tree[i].l==tree[i].r)
		tree[i].len=0;
	else
		tree[i].len=tree[i<<1].len+tree[(i<<1)+1].len;
}
void update(int i,int l,int r,int val){
	if(l<=tree[i].l&&tree[i].r<=r){
		tree[i].cnt+=val;
		pushdown(i);
		return;
	}
	if(r<tree[i].l||l>tree[i].r)
		return;
	update(i<<1,l,r,val);
	update((i<<1)+1,l,r,val);
	pushdown(i);
}
int main(){
	int n,flag=0,fff=1;
	while(cin>>n&&n){
		flag=0;
		double x1,y1,x2,y2;
		for(int i=0;i<n;i++){
			cin>>x1>>y1>>x2>>y2;
			x[flag]=x1;
			e[flag].l=x1;e[flag].r=x2;e[flag].h=y1;e[flag].f=1;
			flag++;
			x[flag]=x2;
			e[flag].l=x1;e[flag].r=x2;e[flag].h=y2;e[flag].f=-1;
			flag++;
		}
//		cout<<"fsadf"<<endl;
		sort(x,x+flag);
		sort(e,e+flag);
		int m=unique(x,x+flag)-x;
		build(1,0,m);
		double sum=0;
//		cout<<flag<<endl;
		for(int i=0;i<flag;i++){
			int l=lower_bound(x,x+m,e[i].l)-x;
			int r=lower_bound(x,x+m,e[i].r)-x-1;
			update(1,l,r,e[i].f);
			sum+=tree[1].len*(e[i+1].h-e[i].h);
//			cout<<tree[1].len<<" "<<e[i+1].h<<" "<<e[i].h<<endl;
//			cout<<sum<<endl;
		}	
		printf("Test case #%d\nTotal explored area: %.2f\n\n",fff++,sum);
	}
}