codevs 3044 矩形面积求并 (扫描线)

/*
之前一直偷懒离散化+暴力做着题 今天搞一下扫描线
自己按照线段树的一般写法写的有些问题
因为不用于以前的区间sum
so
题解搬运者23333
Orz~ 去掉了打标记的过程
同时更新区间的时候先判断是不是已经需要赋值
还有一些细节的处理
线段树是离散化之后的x轴建的
每个线段的权值转移到点上
每个点代表他右侧一小段的长度
所以修改[l,r]变为[l,r-1]
另外维护lazy 表示这个区间压了几次
只要lazy[k]>0 s[k]就存着值
碰到顶边就lazy--
每次计算面积用的是s[1] 也就是整个线段的覆盖部分
对于每次的修改时候查询的时候只是上传 最后拿s[1]计算
所以不用下放lazy了就
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 1010
#define lc k*2
#define rc k*2+1
#define mid (l+r)/2
using namespace std;
int n,m,lazy[maxn*];
double B[maxn],s[maxn*],ans;
struct node{
double x1,x2,y;
int falg;
}A[maxn];
int cmp(const node &x,const node &y){
return x.y<y.y;
}
void up(int k,int l,int r){
if(lazy[k])s[k]=B[r+]-B[l];
else if(l==r)s[k]=;
else s[k]=s[lc]+s[rc];
}
void Change(int k,int l,int r,int x,int y,int z){
if(x<=l&&y>=r){
lazy[k]+=z;up(k,l,r);return;
}
if(x<=mid)Change(lc,l,mid,x,y,z);
if(y>mid)Change(rc,mid+,r,x,y,z);
up(k,l,r);
}
int main()
{
while(){
scanf("%d",&n);
if(n==)break;m=;
memset(s,,sizeof(s));
memset(lazy,,sizeof(lazy));
double a,b,c,d;
int l,r;ans=;
for(int i=;i<=n;i++){
scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
A[++m].x1=a;A[m].x2=c;A[m].y=b;A[m].falg=;B[m]=a;
A[++m].x1=a;A[m].x2=c;A[m].y=d;A[m].falg=-;B[m]=c;
}
sort(B+,B++m);sort(A+,A++m,cmp);
for(int i=;i<=m;i++){
l=lower_bound(B+,B++m,A[i].x1)-B;
r=lower_bound(B+,B++m,A[i].x2)-B-;
if(l<=r)Change(,,m,l,r,A[i].falg);
ans+=(double)(s[]*(A[i+].y-A[i].y));
}
printf("%.2f\n",ans);
}
return ;
}
上一篇:初学Python——Socket网络编程


下一篇:JavaScript复习笔记——数据类型