题目链接
segment tree, scanning line
题意
矩形面积的并
分析
最基础的扫描线求矩形面积并的题，离散化后用线段树，这个思想很简单，不再赘述。记录在这里主要是这个线段树的写法，适用于区间反复覆盖，RE了很多次，记在这里方便以后查看。
AC代码
//HDU 1542 Atlantis
//AC 2016-10-19 22:33:31
//Segment tree, scan line
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <set>
#include <string>
#include <map>
#include <queue>
#include <deque>
#include <list>
#include <sstream>
#include <stack>
using namespace std;
#define cls(x) memset(x,0,sizeof x)
#define inf(x) memset(x,0x3f,sizeof x)
#define neg(x) memset(x,-1,sizeof x)
#define ninf(x) memset(x,0xc0,sizeof x)
#define st0(x) memset(x,false,sizeof x)
#define st1(x) memset(x,true,sizeof x)
#define lowbit(x) x&(-x)
#define input(x) scanf("%d",&(x))
#define inputt(x,y) scanf("%d %d",&(x),&(y))
#define bug cout<<"here"<<endl;
//#pragma comment(linker, "/STACK:1024000000,1024000000")//stack expansion
//#define debug
const double PI=acos(-1.0);
const int INF=0x3f3f3f3f;//1061109567-2147483647
const long long LINF=0x3f3f3f3f3f3f3f3f;//4557430888798830399-9223372036854775807
const int maxn=200;
int n,p1;
double pos[2*maxn];
void discrete()
{
sort(pos,pos+2*n);
p1=0;
for(int i=0;i<2*n;++i)
if(pos[p1]!=pos[i])
pos[++p1]=pos[i];
return;
}
struct edge
{
double a,b,x;
int side;
bool operator< (const edge &rhs) const
{
return x<rhs.x;
}
}edges[2*maxn];
/* 线段树 */
struct segNode
{
int left,right;//结点对应的区间端点
/*结点的性质*/
double len;
int lazy;
};
struct segTree
{
segNode tree[maxn*4+10];
/* 由子结点回溯 */
void Push_Up(int x)
{
tree[x].len=tree[x<<1].len+tree[x<<1|1].len;
return;
}
/* 向下更新 */
void Push_Down(int x)
{
if(tree[x].lazy)
{
tree[x<<1].len=pos[tree[x<<1].right+1]-pos[tree[x<<1].left];
tree[x<<1|1].len=pos[tree[x<<1|1].right+1]-pos[tree[x<<1|1].left];
tree[x<<1].lazy+=tree[x].lazy;
tree[x<<1|1].lazy+=tree[x].lazy;
tree[x].lazy=0;
}
}
/* 线段树构造函数 */
void build(int x,int left,int right)
{
tree[x].left=left;
tree[x].right=right;
tree[x].len=0;
tree[x].lazy=0;
if(left==right)//只有一个元素时
return;
/*递归构造子树*/
int mid=(left+right)>>1;
build(x<<1,left,mid);
build(x<<1|1,mid+1,right);
/* 回溯构造 */
Push_Up(x);
return;
}
/* 成段更新 */
void update(int x,int start,int endd,int v)
{
if(start==tree[x].left&&endd==tree[x].right&&tree[x].lazy+v>=0)
{
if(tree[x].lazy+v>=0)
{
tree[x].lazy+=v;
v=0;
}
else
{
v+=tree[x].lazy;
tree[x].lazy=0;
}
if(tree[x].lazy)
tree[x].len=pos[tree[x].right+1]-pos[tree[x].left];
else if(start==endd)
tree[x].len=0;
else
Push_Up(x);
if(!v)
return;
}
Push_Down(x);//需要子节点的真实信息
int mid=(tree[x].left+tree[x].right)>>1;
if(endd<=mid)//更新区间完全在左子结点中
update(x<<1,start,endd,v);
else if(start>mid)//更新区间完全在右子结点中
update(x<<1|1,start,endd,v);
else
{
update(x<<1,start,mid,v);
update(x<<1|1,mid+1,endd,v);
}
Push_Up(x);//回溯更新
}
}area;
int main()
{
//ios::sync_with_stdio(false);
//cin.tie(0);
#ifdef debug
freopen("E:\Documents\code\input.txt","r",stdin);
freopen("E:\Documents\code\output.txt","w",stdout);
#endif
//IO
for(int kase=1;input(n)!=EOF&&n;++kase)
{
for(int i=0;i<n;++i)
{
scanf("%lf%lf%lf%lf",&edges[i<<1].x,&pos[i<<1],&edges[i<<1|1].x,&pos[i<<1|1]);
edges[i<<1].a=edges[i<<1|1].a=pos[i<<1];
edges[i<<1|1].b=edges[i<<1].b=pos[i<<1|1];
edges[i<<1].side=1;
edges[i<<1|1].side=-1;
}
discrete();
sort(edges,edges+2*n);
area.build(1,0,p1);
double ans=0;
int e1,e2;
for(int i=0;i<2*n-1;++i)
{
e1=lower_bound(pos,pos+p1+1,edges[i].a)-pos;
e2=lower_bound(pos,pos+p1+1,edges[i].b)-pos-1;
area.update(1,e1,e2,edges[i].side);
ans+=(edges[i+1].x-edges[i].x)*area.tree[1].len;
}
printf("Test case #%d
Total explored area: %.2f
",kase,ans);
}
return 0;
}