扫描线
扫描线算法用处很多，一般是求矩形在二维数轴上的一些求解，现在来讲下最基础的一种，矩形面积并
首先我们要知道扫描线的执行过程是怎么样的，他顾名思义就是一条直线从x或者y轴往正方向扫
先看图
首先我们看原图三个矩形在这相交，但是重合面积我们不进行运算
然后我们有一条扫描线平行于x轴一直向上扫
我们会对每条边加个权值，入边为1，出边为-1，那么我们对第一条边进行插入，那么我们线段树就会新加入紫色那段区间，区间值+1，然后我们计算这条边的时候，我们之前求出了每条入边出边
的高度，那么我们就会知道这一段的面积
计算方法就是 区间长度*（edg[i+1].h-edg[i].h）
其他部分也类似，因为我们把出边的值置为了-1，那么就可以利用这个和值为0的道理，达到删边的操作
然后这东西一般联合二维离散化一起使用
下面来个代码
#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<cstdlib> #include<algorithm> #define mem(a,b) memset(a,b,sizeof(a)) #define inf 0x3f3f3f3f #define N 220 #define ll long long using namespace std; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 struct Seg { double l,r,h; int f; Seg() {} Seg(double a,double b,double c,int d):l(a),r(b),h(c),f(d) {} bool operator < (const Seg &cmp) const { return h<cmp.h; } } e[N]; struct node { int cnt; double len; } t[N<<2]; double X[N]; void pushdown(int l,int r,int rt) { if(t[rt].cnt)//当前的边被标记，就把当前的长度加上 t[rt].len=X[r+1]-X[l]; else if(l==r)//当为一个点的时候长度为0 t[rt].len=0; else//其他情况把左右两个区间的值加上 t[rt].len=t[rt<<1].len+t[rt<<1|1].len; } void update(int L,int R,int l,int r,int rt,int val) { if(L<=l&&r<=R) { t[rt].cnt+=val;//加上标记的值 pushdown(l,r,rt);//像下更新节点 return; } int m=(l+r)>>1; if(L<=m) update(L,R,lson,val); if(R>m) update(L,R,rson,val); pushdown(l,r,rt); } int main() { int n,q=1; double a,b,c,d; while(~scanf("%d",&n)&&n) { mem(t,0); int num=0; for(int i=0; i<n; i++) { scanf("%lf%lf%lf%lf",&a,&b,&c,&d); X[num]=a; e[num++]=Seg(a,c,b,1);//矩形下面用1来标记吗 X[num]=c; e[num++]=Seg(a,c,d,-1);//上面用-1来标记 } sort(X,X+num);//用于离散化 sort(e,e+num);//把矩形的边的纵坐标从小到大排序 int m=unique(X,X+num)-X; double ans=0; for(int i=0; i<num; 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(l,r,0,m,1,e[i].f); ans+=t[1].len*(e[i+1].h-e[i].h); } printf("Test case #%d Total explored area: %.2lf ",q++,ans); } return 0; }