hdu1255 覆盖的面积 线段树+里离散化求矩形面积的交

时间:2021-02-07 09:55:23

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1255

求矩形面积的交的线段树题目,刚做了求并的题目,再做这个刚觉良好啊,只要再加一个表示覆盖次数大于1次的长度变量即可

代码:

 #include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
class node
{
public:
int l,r;
int c;
double cnt;
double more ;//表示被覆盖次数大于一次的长度
double lf,rf;
};
node segTree[maxn*];
class line
{
public:
double x,y1,y2;
int f;
};
line le[maxn*];
bool cmp(line a, line b)
{
return a.x< b.x;
}
double y[maxn*]; void build(int num,int l, int r)
{
segTree[num].l=l;
segTree[num].r=r;
segTree[num].cnt=;
segTree[num].more==;
segTree[num].lf=y[l];
segTree[num].rf=y[r];
if(l+==r) return;
int mid=(l+r)/;
build(num*,l,mid);
build(num*+,mid,r); } void calen(int num)
{
if(segTree[num].c >=)
{
segTree[num].more=segTree[num].cnt=segTree[num].rf-segTree[num].lf;
return ;
}
else if(segTree[num].c==)
{
segTree[num].cnt=segTree[num].rf-segTree[num].lf;
if(segTree[num].l+ ==segTree[num].r) segTree[num].more=;
else segTree[num].more=segTree[num*].cnt+segTree[num*+].cnt;
}
else
{
if(segTree[num].l+ ==segTree[num].r )
{
segTree[num].cnt=segTree[num].more=;
}
else
{
segTree[num].cnt=segTree[num*].cnt+segTree[num*+].cnt;
segTree[num].more=segTree[num*].more+segTree[num*+].more;
}
}
}
void update(int num, line e)
{
if(e.y1 == segTree[num].lf && e.y2==segTree[num].rf)
{
segTree[num].c+=e.f;
calen(num);
return ;
}
if(e.y2 <= segTree[num*].rf) update(num*,e);
else if(e.y1 >= segTree[num*+].lf) update(num*+,e);
else
{
line temp=e;
temp.y2=segTree[num*].rf;
update(num*,temp);
temp=e;
temp.y1=segTree[num*+].lf;
update(num*+,temp);
}
calen(num);
}
int main()
{
int t;
int n;
double x1,x2,y1,y2; scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
int num=;
for(int i=;i<=n;i++)
{
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
le[num].x=x1;
le[num].y1=y1;
le[num].y2=y2;
le[num].f=;
y[num]=y1;
num++;
le[num].x=x2;
le[num].y1=y1;
le[num].y2=y2;
le[num].f=-;
y[num]=y2;
num++;
}
sort(le+,le+num,cmp);
sort(y+,y+num);
build(,,num-);
update(,le[]);
double ans=;
for(int i=;i<num;i++)
{
ans+=segTree[].more*(le[i].x - le[i-].x);
update(,le[i]);
}
printf("%.2lf\n",ans);
}
return ; }