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内容请搜索靠谱客的其他文章。