首页 > 代码库 > HDU 1828——Picture（线段树+周长并+扫描线）

HDU 1828——Picture（线段树+周长并+扫描线）

2024-07-24 05:22:20   222人阅读

Picture

Time Limit: 6000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2902    Accepted Submission(s): 1533


Problem 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.

Please process to the end of file.
 

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
 



—————————————————————分割线————————————————————


题目大意：

给你n个矩形，保证这些矩形都是水平或者垂直的，求这些矩形所围成图形的周长


思路：

结构体保存矩形的左右端点，高度，下底边为1，上底边为-1

对矩形的高度从小到大排序，用一根扫描线从下往上扫


1、求底边：

周长并是长加宽，对于面积并中，已经知道每次覆盖区间线段长度，那么只要保存上一次的长度，那么这次和上一次的差值就是每次增加的线段长。即是底边


2、求高：

已知底边的长度，那么只要记录底边是由多少条连续区间线段构成的，假如为m，那么宽的数量就是m*2了。画画图

那么怎么求得连续子区间的数量？

一个节点的连续子区间的数量=左二子的连续区间数量+右儿子连续区间数量-（中间区间是否相连）

怎么判断中间区间是否相连？ 记录一个区间的左右端点是否存在，如果左二子的右端点和右儿子的左端点都存在，则表明中间是连续的


仍然点表示线段，更新线段树的时候右端点-1，计算的时候把线段变为点  所以len[rt]=r-l+1


代码中保存节点信息的数组并没有初始化，因为根本没必要，是为什么呢？想想就知道了

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn=20001;
using namespace std;
int cnt[maxn<<2],len[maxn<<2],numseg[maxn<<2];
bool lbd[maxn<<2],rbd[maxn<<2];
struct Seg
{
    int l,r,h;
    int s;
    Seg(){};
    Seg(int a,int b,int c,int d):l(a),r(b),h(c),s(d){};
    bool operator<(const Seg&cmp)const{
        return h<cmp.h;
    }
}ss[maxn];
void push_up(int rt,int l,int r)
{
    if(cnt[rt]){
        len[rt]=r-l+1;
        numseg[rt]=lbd[rt]=rbd[rt]=1;
    }
    else if(l==r){
        len[rt]=numseg[rt]=lbd[rt]=rbd[rt]=0;
    }
    else {
        lbd[rt]=lbd[rt<<1];
        rbd[rt]=rbd[rt<<1|1];
        len[rt]=len[rt<<1]+len[rt<<1|1];
        numseg[rt]=numseg[rt<<1]+numseg[rt<<1|1]-lbd[rt<<1|1]*rbd[rt<<1];
    }
}
void update(int L,int R,int c,int l,int r,int rt)
{
    if(L<=l&&r<=R){
        cnt[rt]+=c;
        push_up(rt,l,r);
        return ;
    }
    int m=(l+r)>>1;
    if(L<=m) update(L,R,c,lson);
    if(m<R) update(L,R,c,rson);
    push_up(rt,l,r);
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF){
        int a,b,c,d,m=0;
        int l_bd=1<<30,r_bd=-1<<30;
        while(n--){
            scanf("%d %d %d %d",&a,&b,&c,&d);
            l_bd=min(l_bd,a),r_bd=max(r_bd,c);
            ss[m++]=Seg(a,c,b,1);
            ss[m++]=Seg(a,c,d,-1);
        }
        sort(ss,ss+m);
        int ret=0,last=0;
        for(int i=0;i<m;++i){
            update(ss[i].l,ss[i].r-1,ss[i].s,l_bd,r_bd,1);
            ret+=numseg[1]*(ss[i+1].h-ss[i].h)*2;
            ret+=abs(len[1]-last);
            last=len[1];
        }
        printf("%d\n",ret);
    }
    return 0;
}


因为一个样例结束后，是计算到上底边的，下个样例开始时是从下底边开始计算的，那么 -1+1=0，就清空了，节点信息是实时更新的。

HDU 1828——Picture（线段树+周长并+扫描线）


联系
我们