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

题意：给你n个矩形，求出矩形周长并

解题思路：分别对竖线和横线做线段树，区间成段更新

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <functional>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;
struct node
{
int x1,x2,y1,y2,flag;
}line1[10009],line2[10009];
int x1,x2,y1,y2;
int n,cnt1,cnt2;
int x[10009],y[10009],xx[20009],yy[20009];
int lazy[10009<<2],ans;
bool cmp1(node a,node b)
{
if(a.y1!=b.y1) return a.y1<b.y1;
else return a.flag>b.flag;
}
bool cmp2(node a,node b)
{
if(a.x1!=b.x1) return a.x1<b.x1;
else return a.flag>b.flag;
}
void update(int k,int l,int r,int ll,int rr,int flag,int type)
{
if(l>=ll&&r<=rr&&lazy[k]!=-1)
{
lazy[k]+=flag;
if(!lazy[k]&&!type) ans+=2*(x[r-1]-x[l-1]);
if(!lazy[k]&&type) ans+=2*(y[r-1]-y[l-1]);
return ;
}
int mid=(l+r)>>1;
if(lazy[k]!=-1) lazy[k<<1]=lazy[k<<1|1]=lazy[k];
if(ll<mid) update(k<<1,l,mid,ll,rr,flag,type);
if(rr>mid) update(k<<1|1,mid,r,ll,rr,flag,type);
if(lazy[k<<1]==lazy[k<<1|1]) lazy[k]=lazy[k<<1];
else lazy[k]=-1;
}
int main()
{
while(~scanf("%d",&n))
{
ans=0,cnt1=cnt2=0;
for(int i=1;i<=n;i++)
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
x[cnt1++]=x1,x[cnt1++]=x2;
y[cnt2++]=y1,y[cnt2++]=y2;
line1[2*i-1]={x1,x2,y1,0,1};
line1[2*i]={x1,x2,y2,0,-1};
line2[2*i-1]={x1,0,y1,y2,1};
line2[2*i]={x2,0,y1,y2,-1};
}
sort(x,x+cnt1);
sort(y,y+cnt2);
cnt1=unique(x,x+cnt1)-x;
cnt2=unique(y,y+cnt2)-y;
for(int i=0;i<cnt1;i++) xx[x[i]+10000]=i+1;
for(int i=0;i<cnt2;i++) yy[y[i]+10000]=i+1;
sort(line1+1,line1+1+2*n,cmp1);
sort(line2+1,line2+1+2*n,cmp2);
memset(lazy,0,sizeof lazy);
for(int i=1;i<=2*n;i++)
{
int l=xx[line1[i].x1+10000];
int r=xx[line1[i].x2+10000];
update(1,1,cnt1,l,r,line1[i].flag,0);
}
memset(lazy,0,sizeof lazy);
for(int i=1;i<=2*n;i++)
{
int l=yy[line2[i].y1+10000];
int r=yy[line2[i].y2+10000];
update(1,1,cnt2,l,r,line2[i].flag,1);
}
printf("%dn",ans);
}
return 0;
}

最后

以上就是寒冷蜜粉为你收集整理的HDU1828-Picture Picture 的全部内容，希望文章能够帮你解决HDU1828-Picture Picture 所遇到的程序开发问题。

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