首页 > ACM题库 > HDU-杭电 > HDU 3265-Posters-线段树-[解题报告]HOJ
2014
03-13

HDU 3265-Posters-线段树-[解题报告]HOJ

Posters

问题描述 :

Ted has a new house with a huge window. In this big summer, Ted decides to decorate the window with some posters to prevent the glare outside. All things that Ted can find are rectangle posters.

However, Ted is such a picky guy that in every poster he finds something ugly. So before he pastes a poster on the window, he cuts a rectangular hole on that poster to remove the ugly part. Ted is also a careless guy so that some of the pasted posters may overlap when he pastes them on the window.

Ted wants to know the total area of the window covered by posters. Now it is your job to figure it out.

To make your job easier, we assume that the window is a rectangle located in a rectangular coordinate system. The window’s bottom-left corner is at position (0, 0) and top-right corner is at position (50000, 50000). The edges of the window, the edges of the posters and the edges of the holes on the posters are all parallel with the coordinate axes.

输入:

The input contains several test cases. For each test case, the first line contains a single integer N (0<N<=50000), representing the total number of posters. Each of the following N lines contains 8 integers x1, y1, x2, y2, x3, y3, x4, y4, showing details about one poster. (x1, y1) is the coordinates of the poster’s bottom-left corner, and (x2, y2) is the coordinates of the poster’s top-right corner. (x3, y3) is the coordinates of the hole’s bottom-left corner, while (x4, y4) is the coordinates of the hole’s top-right corner. It is guaranteed that 0<=xi, yi<=50000(i=1…4) and x1<=x3<x4<=x2, y1<=y3<y4<=y2.

The input ends with a line of single zero.

输出:

The input contains several test cases. For each test case, the first line contains a single integer N (0<N<=50000), representing the total number of posters. Each of the following N lines contains 8 integers x1, y1, x2, y2, x3, y3, x4, y4, showing details about one poster. (x1, y1) is the coordinates of the poster’s bottom-left corner, and (x2, y2) is the coordinates of the poster’s top-right corner. (x3, y3) is the coordinates of the hole’s bottom-left corner, while (x4, y4) is the coordinates of the hole’s top-right corner. It is guaranteed that 0<=xi, yi<=50000(i=1…4) and x1<=x3<x4<=x2, y1<=y3<y4<=y2.

The input ends with a line of single zero.

样例输入:

2
0 0 10 10 1 1 9 9
2 2 8 8 3 3 7 7
0

样例输出:

56

/*
hdu 3265 Posters 线段树+扫描线
用一些中间有矩形洞的矩形海报去糊窗户
文被覆盖的面积

线段树+扫描线
可以简单看一下扫面线,这里只是简单应用(因为边只有水平、垂直两种,所以不用y=y+1地扫,也不用在求交点)

在水平方向上做线段树,进行扫描

每个矩形记录两条边,底边给这段涂上颜色,顶边把颜色去掉

对于大数据,c++的容器的速度还真不敢恭维,以后还是用c吧
改c的时候读x3的时候忘了&

其中还出现几次 Runtime Error(STACK_OVERFLOW)  是因为maxx写成了5555
*/
#include<iostream>
#include<vector>
#include <algorithm>
using namespace std;
const int maxx=55555;
struct node
{
    __int64 sum,color;
}tree[maxx<<3];
struct seg
{
    int x1,x2,y,color;
    seg(int a,int b,int c,int d):x1(a),x2(b),y(c),color(d){}
    bool operator < (const seg &t)const{
        return y < t.y;
    }
};
void pushUp(int no,int l,int r)
{
    if(tree[no].color) tree[no].sum=r-l+1;
    else if(l==r) tree[no].sum=0;
    else tree[no].sum=tree[no<<1].sum+tree[no<<1|1].sum;
}
void update(int x1,int x2,int color,int l,int r,int no)
{
    if(x1<=l&&r<=x2)//整个区间涂上颜色或去掉颜色
    {
        tree[no].color+=color;
        pushUp(no,l,r);//更新所涂长度
        return;
    }
    int m=(l+r)>>1;//左右分别
    if(x1<=m) update(x1,x2,color,l,m,no<<1);//注意等号
    if(x2>m) update(x1,x2,color,m+1,r,no<<1|1);
    pushUp(no,l,r);
}
int main()
{
    int n,x1,x2,x3,x4,y1,y2,y3,y4,i;
    while(cin>>n,n)
    {
        vector<seg> v;
        for(i=1;i<=n;++i)
        {
            cin>>x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4;
            if(x1<x3)//拆成四个矩形
            {
                v.push_back(seg(x1,x3,y1,1));//底边给这段涂上颜色,
                v.push_back(seg(x1,x3,y2,-1));//顶边把颜色去掉
            }
            if(x4<x2)
            {
                v.push_back(seg(x4,x2,y1,1));
                v.push_back(seg(x4,x2,y2,-1));
            }
            if(y1<y3)
            {
                v.push_back(seg(x3,x4,y1,1));
                v.push_back(seg(x3,x4,y3,-1));
            }
            if(y4<y2)
            {
                v.push_back(seg(x3,x4,y4,1));
                v.push_back(seg(x3,x4,y2,-1));
            }
        }
        sort(v.begin(),v.end());//从小到大排序,从小的开始扫描
        memset(tree,0,sizeof(tree));
        __int64 ret=0;
        int end=v.size();
        for(i=0;i<end-1;++i)
        {
            if(v[i].x2>v[i].x1)
                update(v[i].x1,v[i].x2-1,v[i].color,0,maxx,1);//对每条边 经行 涂颜色或去颜色  注意第二个参数-1    左闭右开,防止一个点算两次
            ret+=tree[1].sum*(v[i+1].y-v[i].y);//根据所涂长度 及 高度差 算面积

        }
        printf("%I64d\n",ret);
    }
    return 0;
}

参考:http://blog.csdn.net/qq172108805/article/details/8790228


  1. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!

  2. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3