覆盖的面积 HDU - 1255 线段树+扫描线+离散化 求特定交叉面积

#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
const int N=;
struct Node
{
double x,yl,yh;
int w;
bool operator<(Node t)const
{
return x<t.x;
} }edge[N];
struct
{
int l,r,cover;
}tr[N];
double ys[N];
void build(int u,int l,int r)
{
int mid=l+r>>;
tr[u].l=l,tr[u].r=r;
tr[u].cover=;
if (r-l>)
{
build(u<<,l,mid);
build(u<<|,mid,r);
}
}
void modify(int u,int l,int r,int val)
{
int mid=tr[u].l+tr[u].r>>;
if(tr[u].l==l&&tr[u].r==r)
{
tr[u].cover+=val;
}
else if(tr[u].r-tr[u].l>)
{
if (l>=mid)
modify(u<<|,l,r,val);
else if(r<=mid)
modify(u<<,l,r,val);
else
{
modify(u<<,l,mid,val);
modify(u<<|,mid,r,val);
}
}
}
void query(int root,double &ans)
{
//如果被覆盖次数大于1
if (tr[root].cover>)
ans+=ys[tr[root].r]-ys[tr[root].l];
//上式不满足时,可能往下的子区间满足,就往下递归
//如果不是叶节点
else if(tr[root].r-tr[root].l>)
{
tr[root<<].cover+=tr[root].cover;
tr[root<<|].cover+=tr[root].cover;
tr[root].cover=;
query(root<<,ans);
query(root<<|,ans);
}
}
int main()
{
int T,N;
double x1,x2,y1,y2,ans,res;
scanf("%d",&T);
while(T--)
{
res=;
map<double,int>mp;
scanf("%d",&N);
for (int i=,j=;i<=N;++i,j+=)
{
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
//入边
edge[j].x=x1,edge[j].yl=y1,edge[j].yh=y2;
edge[j].w=;
//出边
edge[j+].x=x2,edge[j+].yl=y1,edge[j+].yh=y2;
edge[j+].w=-;
//扫描线
ys[j]=y1,ys[j+]=y2; }
//按x排序
sort(edge+,edge++*N);
//y离散化
sort(ys+,ys++*N);
int cnt=unique(ys+,ys++*N)-(ys+);
build(,,cnt);
//离散化
//映射之后的编号 ,查询的实话再映射到ys中去
for (int i=;i<=cnt;++i)
mp[ys[i]]=i;
for (int i=;i<*N;++i)
{
ans=;
//插进去
modify(,mp[edge[i].yl],mp[edge[i].yh],edge[i].w);
query(,ans);
res+=ans*(edge[i+].x-edge[i].x);
}
printf("%.2lf\n",res);
}
return ;
}
上一篇:PCL—低层次视觉—关键点检测(iss&Trajkovic)


下一篇:洗礼灵魂,修炼python(75)--全栈项目实战篇(3)—— 账户注册登录管理系统