【poj1177&&hdu1828】Picture

2015.04.17 11:31 Fri | 2次阅读 | 旧日oi | 固定链接 | 源码

Description
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.
Input
Your program is to read from standard input. The first line contains the number of rectangles pasted on the wall. In each of the subsequent lines, one can find the integer coordinates of the lower left vertex and the upper right vertex of each rectangle. The values of those coordinates are given as ordered pairs consisting of an x-coordinate followed by a y-coordinate.0 <= number of rectangles < 5000
All coordinates are in the range [-10000,10000] and any existing rectangle has a positive area.
Output
Your program is to write to standard output. The output must contain a single line with a non-negative integer which corresponds to the perimeter for the input rectangles.
Sample Input
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
Sample Output
228
题解
网上有的代码是错的……当然我也不保证我的一定对。。
这道题求的是矩形的并的周长和
和求面积的方法挺像的。
求面积是用两段的高度之差*当前底边的长度
求周长可以分成两部分,第一部分是x方向,大小为abs(len[1]-pre),pre是上次的len[1]。
求y方向的贡献比较复杂,我们需要维护出len[1]中有多少段互不相交的线段。我们记录三个数组num,lc,rc
num记录的是区间内不相交的线段个数,lc记录左端点是否被覆盖,rc记录右端点是否被覆盖
更新的时候看代码吧
补充:注意边重合的时候要先加边再删边,否则答案会变大!!!!!!!!

我的程序

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define maxn 5005
#define ll long long
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
using namespace std;
int n,x1,x2,x3,x4,y,y2,y3,y4,cnt;
ll ans;
int len[maxn<<4],cover[maxn<<4],num[maxn<<4],lc[maxn<<4],rc[maxn<<4];
struct Line{
    int l,r,h,flag;
}line[maxn*10];
int p[maxn*10];
void add(int x,int y,int xx,int yy)
{
    line[++cnt].l=x;
    line[cnt].r=xx;
    line[cnt].h=y;
    line[cnt].flag=1;
    p[cnt]=x;
    line[++cnt].l=x;
    line[cnt].r=xx;
    line[cnt].h=yy;
    line[cnt].flag=-1;
    p[cnt]=xx;
}
bool cmp(const Line &a,const Line &b)
{
    return a.h<b.h||(a.h==b.h&&a.flag>b.flag);
}
void pushup(int l,int r,int rt)
{
    if(cover[rt]) 
    {
        len[rt]=p[r+1]-p[l];//正常求长度 
        lc[rt]=rc[rt]=1;//整个区间被覆盖,左右都被覆盖 
        num[rt]=1;//有一个不相交线段
    }
    else if(l==r) //这段不说了 
    {
        len[rt]=0;
        lc[rt]=rc[rt]=0;
        num[rt]=0;
    }
    else 
    {
        len[rt]=len[rt<<1]+len[rt<<1|1];//正常求长度 
        lc[rt]=lc[rt<<1];rc[rt]=rc[rt<<1|1];//如果左区间的左端点被覆盖,
                                            //则本区间的左端点依然被覆盖 
                                            //右端点同理 
        num[rt]=num[rt<<1]+num[rt<<1|1]-rc[rt<<1]*lc[rt<<1|1];
        //左区间的不相交线段数+右区间不相交线段数
        //若左区间的右端点被覆盖,右区间的左端点被覆盖,则两个区间只能算一个 
    }
}
void update(int l,int r,int rt,int L,int R,int flag)
{
    if(L>R) return;
    if(L<=l&&R>=r)
    {
        cover[rt]+=flag;
        pushup(l,r,rt);
        return;
    }
    int mid=(l+r)>>1;
    if(mid>=L) update(lson,L,R,flag);
    if(R>mid) update(rson,L,R,flag);
    pushup(l,r,rt);
}
void Init()
{
    cnt=ans=0;
    memset(lc,0,sizeof(lc));
    memset(rc,0,sizeof(rc));
    memset(len,0,sizeof(len));
    memset(num,0,sizeof(num));
    memset(cover,0,sizeof(cover));
}
int main()
{
    while(cin>>n)
    {
        Init();
        for(int i=1;i<=n;i++)
        {  
            scanf("%d%d%d%d",&x1,&y,&x2,&y2);
            add(x1,y,x2,y2);
        }  
        sort(p+1,p+cnt+1);
        sort(line+1,line+cnt+1,cmp);
        int m=1;
        for(int i=2;i<=cnt;i++)
        if(p[i]!=p[i-1]) p[++m]=p[i];
        for(int pre=0,l,r,i=1;i<=cnt;i++)
        {  
            l=lower_bound(p+1,p+m+1,line[i].l)-p;
            r=lower_bound(p+1,p+m+1,line[i].r)-p;
            update(1,m-1,1,l,r-1,line[i].flag);
            ans+=abs(len[1]-pre);pre=len[1];
            if(i<cnt) ans+=num[1]*(line[i+1].h-line[i].h)*2;
        }  
        printf("%lld\n",ans);
    }
    return 0;
}```