我是靠谱客的博主 结实小熊猫，最近开发中收集的这篇文章主要介绍Atlantis HDU - 1542 + 覆盖的面积 HDU - 1255 + Picture HDU - 1828，觉得挺不错的，现在分享给大家，希望可以做个参考。
概述
点击打开链接
点击打开链接
点击打开链接
扫描线求矩形面积的并与交 这类问题之前一直都是更新到底 数据稍强就会T
求周长会用到区间合并
详解点击打开链接
存模板
hdu1542
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct node1
{
double l;
double r;
double h;
int f;
};
struct node2
{
double l;
double r;
double val;
int f;
int leaf;
};
node1 line[100010];
node2 tree[800010];
double pre[200010];
int n;
bool cmp(node1 n1,node1 n2)
{
return n1.h<n2.h;
}
void build(int l,int r,int cur)
{
int m;
tree[cur].l=pre[l];
tree[cur].r=pre[r];
tree[cur].val=0;
tree[cur].f=0;
tree[cur].leaf=0;
if(l+1==r)
{
tree[cur].leaf=1;
return;
}
m=(l+r)/2;
build(l,m,cur*2);
build(m,r,cur*2+1);
return;
}
void pushup(int cur)
{
if(tree[cur].f>0)
{
tree[cur].val=tree[cur].r-tree[cur].l;
}
else
{
if(tree[cur].leaf) tree[cur].val=0;
else tree[cur].val=tree[2*cur].val+tree[2*cur+1].val;
}
return;
}
void scan(double pl,double pr,int f,int cur)
{
if(pl<=tree[cur].l&&tree[cur].r<=pr)
{
tree[cur].f+=f;
pushup(cur);
return;
}
if(pl<tree[cur*2].r) scan(pl,pr,f,cur*2);
if(pr>tree[cur*2+1].l) scan(pl,pr,f,cur*2+1);
pushup(cur);
return;
}
int main()
{
double ans,x1,y1,x2,y2;
int i,j,cas;
cas=1;
while(scanf("%d",&n)!=EOF)
{
if(n==0) break;
for(i=1;i<=n;i++)
{
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
line[2*i-1].l=x1,line[2*i-1].r=x2,line[2*i-1].h=y1,line[2*i-1].f=1;
line[2*i].l=x1,line[2*i].r=x2,line[2*i].h=y2,line[2*i].f=-1;
pre[2*i-1]=x1,pre[2*i]=x2;
}
sort(line+1,line+2*n+1,cmp);
sort(pre+1,pre+2*n+1);
for(i=1,j=0;i<=2*n;i++)
{
if(j==0||pre[i]!=pre[j])
{
j++;
pre[j]=pre[i];
}
}
build(1,j,1);
scan(line[1].l,line[1].r,line[1].f,1);
ans=0;
for(i=2;i<=2*n;i++)
{
ans+=tree[1].val*(line[i].h-line[i-1].h);
scan(line[i].l,line[i].r,line[i].f,1);
}
printf("Test case #%dn",cas++);
printf("Total explored area: %.2fnn",ans);
}
return 0;
}
hdu1255
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct node1
{
double l;
double r;
double h;
int f;
};
struct node2
{
double l;
double r;
double val1;
double val2;
int f;
int leaf;
};
node1 line[2010];
node2 tree[8010];
double pre[2010];
int n;
bool cmp(node1 n1,node1 n2)
{
return n1.h<n2.h;
}
void build(int l,int r,int cur)
{
int m;
tree[cur].l=pre[l];
tree[cur].r=pre[r];
tree[cur].val1=0;
tree[cur].val2=0;
tree[cur].f=0;
tree[cur].leaf=0;
if(l+1==r)
{
tree[cur].leaf=1;
return;
}
m=(l+r)/2;
build(l,m,cur*2);
build(m,r,cur*2+1);
return;
}
void pushup(int cur)
{
if(tree[cur].f>1)
{
tree[cur].val1=tree[cur].val2=tree[cur].r-tree[cur].l;
}
else if(tree[cur].f==1)
{
tree[cur].val1=tree[cur].r-tree[cur].l;
if(tree[cur].leaf) tree[cur].val2=0;
else tree[cur].val2=tree[cur*2].val1+tree[cur*2+1].val1;
}
else
{
if(tree[cur].leaf)
{
tree[cur].val1=tree[cur].val2=0;
}
else
{
tree[cur].val1=tree[cur*2].val1+tree[cur*2+1].val1;
tree[cur].val2=tree[cur*2].val2+tree[cur*2+1].val2;
}
}
return;
}
void scan(double pl,double pr,int f,int cur)
{
if(pl<=tree[cur].l&&tree[cur].r<=pr)
{
tree[cur].f+=f;
pushup(cur);
return;
}
if(pl<tree[cur*2].r) scan(pl,pr,f,cur*2);
if(pr>tree[cur*2+1].l) scan(pl,pr,f,cur*2+1);
pushup(cur);
return;
}
int main()
{
double ans,x1,y1,x2,y2;
int t,cas,i,j;
scanf("%d",&t);
for(cas=1;cas<=t;cas++)
{
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
line[2*i-1].l=x1,line[2*i-1].r=x2,line[2*i-1].h=y1,line[2*i-1].f=1;
line[2*i].l=x1,line[2*i].r=x2,line[2*i].h=y2,line[2*i].f=-1;
pre[2*i-1]=x1,pre[2*i]=x2;
}
sort(line+1,line+2*n+1,cmp);
sort(pre+1,pre+2*n+1);
for(i=1,j=0;i<=2*n;i++)
{
if(j==0||pre[i]!=pre[j])
{
j++;
pre[j]=pre[i];
}
}
build(1,j,1);
scan(line[1].l,line[1].r,line[1].f,1);
ans=0;
for(i=2;i<=2*n;i++)
{
ans+=tree[1].val2*(line[i].h-line[i-1].h);
scan(line[i].l,line[i].r,line[i].f,1);
}
printf("%.2fn",ans);
}
return 0;
}
hdu1828
#include <bits/stdc++.h>
using namespace std;
struct node1
{
int l;
int r;
int h;
int f;
};
struct node2
{
int l;
int r;
int f;
int val;
int left;
int right;
int all;
int leaf;
};
node1 line[10010];
node2 tree[40010];
int pre[10010];
int n;
bool cmp(node1 n1,node1 n2)
{
return n1.h<n2.h;
}
void pushup(int cur)
{
if(tree[cur].f>0)
{
tree[cur].val=tree[cur].r-tree[cur].l;
tree[cur].all=tree[cur].left=tree[cur].right=1;
}
else if(tree[cur].leaf)
{
tree[cur].val=0;
tree[cur].all=tree[cur].left=tree[cur].right=0;
}
else
{
tree[cur].val=tree[2*cur].val+tree[2*cur+1].val;
tree[cur].left=tree[2*cur].left;
tree[cur].right=tree[2*cur+1].right;
tree[cur].all=tree[2*cur].all+tree[2*cur+1].all-tree[2*cur].right*tree[2*cur+1].left;
}
return;
}
void build(int l,int r,int cur)
{
int m;
tree[cur].l=pre[l];
tree[cur].r=pre[r];
tree[cur].f=0;
tree[cur].val=0;
tree[cur].left=0;
tree[cur].right=0;
tree[cur].all=0;
tree[cur].leaf=0;
if(l+1==r)
{
tree[cur].leaf=1;
return;
}
m=(l+r)/2;
build(l,m,2*cur);
build(m,r,2*cur+1);
return;
}
void update(int pl,int pr,int f,int cur)
{
if(pl<=tree[cur].l&&tree[cur].r<=pr)
{
tree[cur].f+=f;
pushup(cur);
return;
}
if(pl<tree[2*cur].r) update(pl,pr,f,2*cur);
if(pr>tree[2*cur+1].l) update(pl,pr,f,2*cur+1);
pushup(cur);
return;
}
int main()
{
int i,j,x1,y1,x2,y2,tem,ans;
while(scanf("%d",&n)!=EOF)
{
for(i=1;i<=n;i++)
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
line[2*i-1].l=x1,line[2*i-1].r=x2,line[2*i-1].h=y1,line[2*i-1].f=1;
line[2*i].l=x1,line[2*i].r=x2,line[2*i].h=y2,line[2*i].f=-1;
pre[2*i-1]=x1,pre[2*i]=x2;
}
sort(line+1,line+2*n+1,cmp);
sort(pre+1,pre+2*n+1);
for(i=1,j=0;i<=2*n;i++)
{
if(j==0||pre[j]!=pre[i])
{
pre[++j]=pre[i];
}
}
build(1,j,1);
tem=0,ans=0;
for(i=1;i<=2*n-1;i++)
{
update(line[i].l,line[i].r,line[i].f,1);
ans+=abs(tree[1].val-tem);
tem=tree[1].val;
ans+=2*tree[1].all*(line[i+1].h-line[i].h);
}
update(line[i].l,line[i].r,line[i].f,1);
ans+=abs(tree[1].val-tem);
printf("%dn",ans);
}
return 0;
}
最后
以上就是结实小熊猫为你收集整理的Atlantis HDU - 1542 + 覆盖的面积 HDU - 1255 + Picture HDU - 1828的全部内容，希望文章能够帮你解决Atlantis HDU - 1542 + 覆盖的面积 HDU - 1255 + Picture HDU - 1828所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复