题目：http://acm.hdu.edu.cn/showproblem.php?pid=1828

题意：给定n（n<=5000）个矩形的顶点坐标，求所有矩形的周长并。

Picture

A number of rectangular posters, photographs and other pictures of the same shape are pasted on a wall. Their sides are all vertical or horizontal. Each rectangle can be partially or totally covered by the others. The length of the boundary of the union of all rectangles is called the perimeter. 

Write a program to calculate the perimeter. An example with 7 rectangles is shown in Figure 1. 



The corresponding boundary is the whole set of line segments drawn in Figure 2. 



The vertices of all rectangles have integer coordinates.

7
-15 0 5 10
-5 8 20 25
15 -4 24 14
0 -6 16 4
2 15 10 22
30 10 36 20
34 0 40 16

228

分析：

还是从下往上扫描线。

那么横着的周长容易统计，往上扫描的时候只需累加此时底边长与上一次算的底边长的差值的绝对值。

竖着的边长怎么求？因为每次扫描线上升的高度已知，只需统计区间内竖边的个数。用线段树的区间合并很好解决，若左孩子的右端点和右孩子的左端点都被覆盖，则区间内的竖边的个数减2。还有，我是用的一个点表示一段区间，比如7就代表[6,7]这个长度为1的区间。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const LL INF = 1e9+7;
const LL MINT = ~0u>>1;
const int maxn = (1e5+6)*4;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
//扫描线，从下往上扫描
struct line
{
int xl,xr,h,d; //线段的左右端点的横坐标，高度，是上底边还是下底边
line(int x1=0,int x2=0,int hh=0,int dd=0):
xl(x1),xr(x2),h(hh),d(dd){}
bool operator < (const line &s)const
{
if(h==s.h)
return d<s.d;
return h<s.h;
}
}s[maxn];
struct node
//线段树节点
{
int sum,cover,num;	//区间覆盖的长度，覆盖的次数,竖线的条数
bool lep,rep;	//左端点是否被覆盖，右端点是否被覆盖
}tree[maxn];
void pushup(int l,int r,int rt)
{
if(tree[rt].cover)
{
tree[rt].sum=r-l+1;
tree[rt].num=2;
tree[rt].lep=tree[rt].rep=true;
}
else if(l==r)
{
tree[rt].sum=tree[rt].lep=tree[rt].rep=tree[rt].num=false;
}
else
{
tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
tree[rt].lep=tree[rt<<1].lep;
tree[rt].rep=tree[rt<<1|1].rep;
tree[rt].num=tree[rt<<1].num+tree[rt<<1|1].num;
if(tree[rt<<1].rep && tree[rt<<1|1].lep)
//左右区间连接
tree[rt].num-=2;
}
}
void update(int L,int R,int c,int l,int r,int rt)
{
if(L<=l && r<=R)
{
tree[rt].cover+=c;
pushup(l,r,rt);
return ;
}
int m=(l+r)>>1;
if(L<=m)
update(L,R,c,lson);
if(R>m)
update(L,R,c,rson);
pushup(l,r,rt);
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
memset(tree,0,sizeof(tree[0])*(n+2));
memset(s,0,sizeof(s[0])*(n+2));
int cnt=0;
for(int i=1;i<=n;i++)
{
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
const int move = 10002;
x1+=move;x2+=move;
//将矩形向右平移
s[++cnt]=line(x1,x2,y1,1);
s[++cnt]=line(x1,x2,y2,-1);
}
sort(s+1,s+cnt+1);
int last=0;
int ans=0;
for(int i=1;i<=cnt;i++)
{
int L=s[i].xl+1;
int R=s[i].xr;
update(L,R,s[i].d,1,30000,1);
ans+=tree[1].num*(s[i+1].h-s[i].h);
ans+=abs(tree[1].sum-last);
last=tree[1].sum;
}
printf("%dn",ans);
}
return 0;
}

最后

以上就是勤奋刺猬为你收集整理的hdu1828 Picture (线段树+扫描线)（求周长并） Picture的全部内容，希望文章能够帮你解决hdu1828 Picture (线段树+扫描线)（求周长并） Picture所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。