首页 > ACM题库 > HDU-杭电 > HDU 1828 Picture -线段树-[解题报告] C++
2013
12-23

HDU 1828 Picture -线段树-[解题报告] C++

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.

输入:

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.

输出:

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.

样例输入:

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

hdu 1828 Picture(扫描线)

题意:算多个矩形的周长并。

线段树,扫描线。。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#define ll __int64
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
using namespace std ;

int max ( int a , int b ) { return a > b ? a : b ; }
int min ( int a , int b ) { return a < b ? a : b ; }
const int maxn = 222222 ;
int sum[maxn<<2] , cnt[maxn<<2] ;

struct Edge
{
    int l , r , h , id ;
    bool operator < ( const Edge &p ) const
    {
        return h < p.h ;
    }
}edge[maxn] ;

struct Rec
{
    int a , b , c , d ;
} rec[maxn] ;

void init ()
{
    memset ( sum , 0 , sizeof ( sum ) ) ;
    memset ( cnt , 0 , sizeof ( cnt ) ) ;
}

void build_seg ( int l , int r , int h , int id , int i )
{
    edge[i].l = l , edge[i].r = r , edge[i].h = h , edge[i].id = id ;
}

void push_up ( int l , int r , int rt )
{
    if ( cnt[rt] ) sum[rt] = r - l + 1 ;
    else if ( l == r ) sum[rt] = 0 ;
    else sum[rt] = sum[rt<<1] + sum[rt<<1|1] ;
}

void update ( int a , int b , int c , int l , int r , int rt )
{
    if ( a <= l && r <= b )
    {
        cnt[rt] += c ;
        push_up ( l , r , rt ) ;
        return ;
    }
    int m = ( l + r ) >> 1 ;
    ll ret = 0 ;
    if ( a <= m ) update ( a , b , c , lson ) ;
    if ( m < b ) update ( a , b , c , rson ) ;
    push_up ( l , r , rt ) ;
}

ll solve ( int m )
{
    init () ;
    ll ret = 0 ;
    sort ( edge + 1 , edge + m + 1 ) ;
    int i , last = 0 ;
    int l = 10001 , r = -10001 ;
    for ( i = 1 ; i <= m ; i ++ ) 
    {
        r = max ( r , edge[i].r ) ;
        l = min ( l , edge[i].l ) ;
    }
    for ( i = 1 ; i <= m ; i ++ )
    {
        update ( edge[i].l , edge[i].r - 1 , edge[i].id , l , r , 1 ) ;
        ret += abs ( last - sum[1] ) ;
        last = sum[1] ;
    }
    return ret ;
}

int main ()
{
    int n , i , j , a , b , c , d ;
    while ( scanf ( "%d" , &n ) != EOF )
    {
        ll ans = 0 ;
        for ( i = 1 ; i <= n ; i ++ )
            scanf ( "%d%d%d%d" , &rec[i].a , &rec[i].b , &rec[i].c , &rec[i].d ) ;
        int m = 0 ;
        for ( i = 1 ; i <= n ; i ++ )
        {
            m ++ ;
            build_seg ( rec[i].a , rec[i].c , rec[i].b , 1 , m ) ;
            m ++ ;
            build_seg ( rec[i].a , rec[i].c , rec[i].d , -1 , m ) ;
        }
        ans += solve ( m ) ;
        m = 0 ;
        for ( i = 1 ; i <= n ; i ++ )
        {
            m ++ ;
            build_seg ( rec[i].b , rec[i].d , rec[i].a , 1 , m ) ;
            m ++ ;
            build_seg ( rec[i].b , rec[i].d , rec[i].c , -1 , m ) ;
        }
        ans += solve ( m ) ;
        printf ( "%I64d\n" , ans ) ;
    }
}

解题报告转自:http://blog.csdn.net/no__stop/article/details/12971035


  1. Gucci New Fall Arrivals

    This is really nice to know. I hope it will be successful in the future. Good job on this and keep up the good work.

  2. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  3. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的