【扫描线+离散+线段树】【面积并&面积交&周长并】HDU - 1542 && HDU - 1255 && HDU - 1828【面积并】HDU - 1542 - Atlantis题目链接题意：题解：【面积交】HDU - 1255 - 覆盖的面积题目链接题意：【周长并】HDU - 1828 - Picture

78 阅读 0 评论 52 点赞

我是靠谱客的博主紧张画笔，最近开发中收集的这篇文章主要介绍【扫描线+离散+线段树】【面积并&面积交&周长并】HDU - 1542 && HDU - 1255 && HDU - 1828【面积并】HDU - 1542 - Atlantis题目链接题意：题解：【面积交】HDU - 1255 - 覆盖的面积题目链接题意：【周长并】HDU - 1828 - Picture，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

【面积并】HDU - 1542 - Atlantis

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

题意：

给出若干个矩形的坐标，矩形之间存在重叠。问所有矩形覆盖的总面积是多少。

题解：

对于每个矩形抽象成两条线，每一个线记录：x轴坐标，上端点坐标，下端点坐标。另外对于每一条线记录一个属性val，如果这个线是矩形左边的线，那么val值为1，右边为-1。然后把这些线段按x轴坐标从左到右排序。

离散y轴，每条线段就是相当于覆盖一定的区间。从左到右扫每条线段，利用线段树维护当前被覆盖的长度sum，sum乘上线段之间的距离就是这一部分所要求的的面积。

因为任何一段区间必定是先+1后-1，所以不会存在负数。这个线段树的节点也可以理解成线段，num记录的就是这条线段覆盖了几次。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e2+7;
struct Edge{
double x;
int up,dw;
int val;
bool operator<(const Edge a)const{
return x<a.x;
}
Edge(double x=0,int up=0,int dw=0,int val=0):x(x),up(up),dw(dw),val(val){}
}e[N*2];
double lx[N],ly[N],rx[N],ry[N];
double y[N*2];
int num[N<<4];
double sum[N<<4];
void pu(int l,int r,int rt){
if(num[rt]) sum[rt]=y[r+1]-y[l];
else if(l==r) sum[rt]=0;
else sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void update(int L,int R,int l,int r,int rt,int val){
if(L<=l&&r<=R){
num[rt]+=val;
pu(l,r,rt);
return;
}
int m=l+r>>1;
if(L<=m) update(L,R,l,m,rt<<1,val);
if(m<R) update(L,R,m+1,r,rt<<1|1,val);
pu(l,r,rt);
}
int main()
{
int n,cs=0;
while(scanf("%d",&n)!=EOF){
if(n==0) break;
memset(sum,0,sizeof(sum));
memset(num,0,sizeof(num));
int cnt=0;
for(int i=1;i<=n;i++){
scanf("%lf%lf%lf%lf",&lx[i],&ly[i],&rx[i],&ry[i]);
y[++cnt]=ly[i];
y[++cnt]=ry[i];
}
sort(y+1,y+1+cnt);
cnt=unique(y+1,y+1+cnt)-y-1;
int tot=0;
for(int i=1;i<=n;i++){
int up=lower_bound(y+1,y+1+cnt,ly[i])-y;
int dw=lower_bound(y+1,y+1+cnt,ry[i])-y;
e[++tot]=Edge(lx[i],up,dw,1);
e[++tot]=Edge(rx[i],up,dw,-1);
}
sort(e+1,e+1+tot);
double ans=0;
for(int i=1;i<=tot;i++){
ans+=sum[1]*(e[i].x-e[i-1].x);
update(e[i].up,e[i].dw-1,1,cnt-1,1,e[i].val);
}
printf("Test case #%dn",++cs);
printf("Total explored area: %.2fnn",ans);
}
}

【面积交】HDU - 1255 - 覆盖的面积

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

题意：

给出若干个矩形，求出至少被覆盖两次的面积。

和上一题思路类似，同样是扫描线离散线段树的处理。

只不过这题线段树处理的要有些不一样，因为要考虑覆盖的次数，我在上面一题的基础上写了pushdown操作来维护。

注意这几点：

如果当前区间覆盖次数不到两次，则需要pushdown且需要往下面的节点继续。
如果父亲节点已经更新过了，因为做过了pushdown操作，那么这个节点不需要更新。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+7;
struct Edge{
double x;
int up,dw;
int val;
bool operator<(const Edge a)const{
return x<a.x;
}
Edge(double x=0,int up=0,int dw=0,int val=0):x(x),up(up),dw(dw),val(val){}
}e[N*2];
double lx[N],ly[N],rx[N],ry[N];
double y[N*2];
int num[N<<4];
int lz[N<<4];
double sum[N<<4];
void pd(int l,int r,int rt){
if(lz[rt]){
int m=l+r>>1;
num[rt<<1]+=lz[rt];
if(num[rt<<1]>1) sum[rt<<1]=y[m+1]-y[l];
else sum[rt]=0;
num[rt<<1|1]+=lz[rt];
if(num[rt<<1|1]>1) sum[rt<<1|1]=y[r+1]-y[m+1];
else sum[rt]=0;
lz[rt<<1]+=lz[rt];
lz[rt<<1|1]+=lz[rt];
lz[rt]=0;
}
}
void pu(int rt){
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void update(int L,int R,int l,int r,int rt,int val,bool flag){
if(L<=l&&r<=R){
if(flag){
num[rt]+=val;
lz[rt]+=val;
}
flag=false;
if(num[rt]>1){
sum[rt]=y[r+1]-y[l];
return;
}
}
if(l==r){
sum[rt]=0;
return;
}
pd(l,r,rt);
int m=l+r>>1;
if(L<=m) update(L,R,l,m,rt<<1,val,flag);
if(m<R) update(L,R,m+1,r,rt<<1|1,val,flag);
pu(rt);
}
int main()
{
int T,n,cs=0;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
memset(sum,0,sizeof(sum));
memset(num,0,sizeof(num));
memset(lz,0,sizeof(lz));
int cnt=0;
for(int i=1;i<=n;i++){
scanf("%lf%lf%lf%lf",&lx[i],&ly[i],&rx[i],&ry[i]);
y[++cnt]=ly[i];
y[++cnt]=ry[i];
}
sort(y+1,y+1+cnt);
cnt=unique(y+1,y+1+cnt)-y-1;
int tot=0;
for(int i=1;i<=n;i++){
int up=lower_bound(y+1,y+1+cnt,ry[i])-y;
int dw=lower_bound(y+1,y+1+cnt,ly[i])-y;
e[++tot]=Edge(lx[i],up,dw,1);
e[++tot]=Edge(rx[i],up,dw,-1);
}
sort(e+1,e+1+tot);
double ans=0;
for(int i=1;i<=tot;i++){
ans+=sum[1]*(e[i].x-e[i-1].x);
update(e[i].dw,e[i].up-1,1,cnt-1,1,e[i].val,1);
}
printf("%.2fn",ans);
}
}

【周长并】HDU - 1828 - Picture

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

题意：

给出一些矩阵，求出所有矩形覆盖形成的图形的周长。

题解：

与面积并类似的解法。

维护当前覆盖的范围sum，abs(sum[i]-sum[i-1])之和是竖线的值（注意最后一条扫面线也要计算）
维护当前有几段区间被覆盖到cnt，cnt乘上扫描线之间的距离是横线的答案。

当然只维护一个，横竖扫两遍也可以。

注意扫描线的排序如果产生了重合，那么插入的优先级要高，不然sum可能会多算。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=5e3+7;
int lx[N],ly[N],rx[N],ry[N];
int y[N*2];
struct Edge{
int le,ri,x;
int val;
Edge(int le=0,int ri=0,int x=0,int val=0):le(le),ri(ri),x(x),val(val){}
bool operator<(const Edge a)const{
if(x==a.x) return val>a.val;
return x<a.x;
}
}e[N*2];
struct Node{
bool ll,rr;
int num,sum,cnt;
}a[N<<4];
void build(int l,int r,int rt){
a[rt].ll=a[rt].rr=false;
a[rt].num=a[rt].sum=a[rt].cnt=0;
if(l==r) return;
int m=l+r>>1;
build(l,m,rt<<1);
build(m+1,r,rt<<1|1);
}
void pu(int l,int r,int rt){
if(a[rt].num){
a[rt].sum=y[r+1]-y[l];
a[rt].cnt=1;
a[rt].ll=a[rt].rr=true;
}
else if(l==r){
a[rt].sum=a[rt].cnt=0;
a[rt].ll=a[rt].rr=false;
}
else{
a[rt].sum=a[rt<<1].sum+a[rt<<1|1].sum;
a[rt].cnt=a[rt<<1].cnt+a[rt<<1|1].cnt;
if(a[rt<<1].rr&&a[rt<<1|1].ll) a[rt].cnt--;
a[rt].ll=a[rt<<1].ll;a[rt].rr=a[rt<<1|1].rr;
}
}
void update(int L,int R,int l,int r,int rt,int val){
if(L<=l&&r<=R){
a[rt].num+=val;
pu(l,r,rt);
return;
}
int m=l+r>>1;
if(L<=m) update(L,R,l,m,rt<<1,val);
if(m<R) update(L,R,m+1,r,rt<<1|1,val);
pu(l,r,rt);
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF){
int ny=0;
for(int i=1;i<=n;i++){
scanf("%d%d%d%d",&lx[i],&ly[i],&rx[i],&ry[i]);
y[++ny]=ly[i];y[++ny]=ry[i];
}
sort(y+1,y+1+ny);
ny=unique(y+1,y+1+ny)-y-1;
build(1,ny-1,1);
int edn=0;
for(int i=1;i<=n;i++){
ly[i]=lower_bound(y+1,y+1+ny,ly[i])-y;
ry[i]=lower_bound(y+1,y+1+ny,ry[i])-y;
e[++edn]=Edge(ly[i],ry[i],lx[i],1);
e[++edn]=Edge(ly[i],ry[i],rx[i],-1);
}
sort(e+1,e+1+edn);
int ans=0,lst=0;
for(int i=1;i<=edn;i++){
ans+=a[1].cnt*2*(e[i].x-e[i-1].x);
update(e[i].le,e[i].ri-1,1,ny-1,1,e[i].val);
ans+=abs(a[1].sum-lst);lst=a[1].sum;
}
printf("%dn",ans);
}
}