hdu 1542 Atlantis (线段树+扫描线求矩形面积并,模板题)

hdu1542题目链接

题意:

求n(100)个矩形的面积并。

思路:

扫描线+线段树

题目是2000年中欧区域赛的题目,虽然年代久远,但是有好几个点还是很值得学习的。

首先是离散化的适用范围:

之前比较常用的是将比较大的整数值离散化,常常是因为数值太大无法作为下标。

那么其实,浮点数有的时候也需要进行离散化,比如作为数组的下标,比如用来枚举。

做法上是和将较大的整数值离散化没有区别,因为遇到的题目不多,所以特意记录一下。

第二点是扫描线的思想:

其实扫描线的思想很早就接触过,noip2011的时候,tyvj上有一道类似的题目,不过是一唯的,当时印象深刻的是@Ocean 兄的那个比喻:

一段公路上右很多区间要收不同的费用,区间的开始给一个标记,表示该段区间对答案有贡献,区间的结束拿走该标记,表示该段区间对答案的贡献结束。

这就是扫描线的思想。

第三个是处理线段覆盖问题的一般做法:

通常线段树的节点处理的都是点,处理线段的时候就会比较麻烦。

  另外很重要的一点就是, 线段树都是维护一个点集, 但是对于边的问题就会变得很麻烦,  我们可以按照区间左端点建立线段树, 那么一个点表示的就不是点了, 而是起点在这个点的一个线段。  这**样的话, 右区间就要相应的-1, 例如更新区间[1, 4], 就相当于更新标号为[1, 3]的线段。**

这也是处理线段覆盖问题的通用方法。

对于上面引用中提到的例子中“更新[1,4],就相当于更新标号为[1,3]的线段”,是因为标号为1的节点代表区间[1,2],标号为2的节点代表区间[2,3],标号为3的节点代表期间[3,4]

接下来具体讨论这道题目的做法:

将矩形按平行x轴方形构建扫描线(只是思想,不用实际构造),

每个矩形2条平行x轴的边分类{上边,下边}2类,如果我们从下往上“扫描”线,那么[下边]就表示了对答案贡献的开始,[下边]就表示了对答案贡献的结束。

  * 扫描线扫描的过程(建议配合代码模拟)
**以下图转载自@kk303的博客**

初始状态

初始状态

这里写图片描述

扫到最下边的线, 点1→3更新为1

这里写图片描述

扫到第二根线, 此时S=lcnt!=0∗h两根线之间, 得到绿色的面积, 加到答案中去, 随后更新计数

这里写图片描述

同上, 将黄色的面积加到答案中去

这里写图片描述

同上, 将灰色的面积加到答案中去

这里写图片描述

同上, 将紫色的面积加到答案中去

这里写图片描述

/* ***********************************************
Author :111qqz
Created Time :2017年09月27日 星期三 16时37分39秒
File Name :1542.cpp
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define PB push_back
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=205;
int n;

double X[N]; //存储所有x坐标,用来离散化。
//扫描线
struct Seg
{
    double l,r,h;
    //表示扫面线的起点,终点,所在的高度(y坐标)
    int d;//1或者-1,表示扫描线对面积是正向影响还是负向影响
    Seg(){}
    Seg(double l,double r,double h,int d):l(l),r(r),h(h),d(d){}
    bool operator < (const Seg &rhs)const
    {
    return h<rhs.h;
    }
    //从下向上处理扫描线。
}seg[N];
struct Tree
{
    int cnt;
    double len;
}tree[N<<2];
void PushUp(int l,int r,int rt)
{
    /*由于线段树的节点表示的其实是长度为1的区间
     * 因此线段树的区间[l,r],对应的点的端点是l,r+1
     */
    if (tree[rt].cnt) tree[rt].len = X[r+1]-X[l]; //当前区间已经完全被线段覆盖
    else if (l==r) tree[rt].len=0; //是叶子节点而且没有被覆盖。
    else tree[rt].len = tree[rt<<1].len + tree[rt<<1|1].len; //没有完全被覆盖,从其子区间获得信息。
}

void update( int L,int R,int v,int l,int r,int rt)
{
    if (L<=l && r<=R)
    {
    tree[rt].cnt+=v;
    PushUp(l,r,rt);
    return;
    }
    int m = (l+r)>>1;
    if (L<=m) update(L,R,v,lson);
    if (R>=m+1) update(L,R,v,rson);
    PushUp(l,r,rt);
}
int main()
{
    #ifndef  ONLINE_JUDGE 
    freopen("./in.txt","r",stdin);
  #endif
    int cas = 0;
    while (~scanf("%d",&n)&&n)
    {
        ms(tree,0);
        for ( int i = 1 ; i <= n ; i++)
        {
        double x1,y1,x2,y2;
        scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
        seg[i] = Seg(x1,x2,y1,1);
        seg[i+n]= Seg(x1,x2,y2,-1);
        X[i] = x1;
        X[i+n] = x2;
        }
        n<<=1;
        sort(X+1,X+n+1);
        int m = unique(X+1,X+1+n)-X-1;
        
        sort(seg+1,seg+n+1);
        double ans = 0;
        for ( int i = 1 ; i < n ; i++)
        {
        int l = lower_bound(X+1,X+1+m,seg[i].l)-X;
        int r = lower_bound(X+1,X+1+m,seg[i].r)-X;
        if (l<r)
        update(l,r-1,seg[i].d,1,m,1);
        ans += tree[1].len * (seg[i+1].h-seg[i].h);
        }
        printf("Test case #%d\nTotal explored area: %.2f\n\n",++cas,ans);
        
    }   

  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}

参考资料:

HDU 1542 Atlantis(线段树:扫描线)

HDU 1542 Atlantis(线段树求矩形面积并)

矩形面积并、矩形面积交、矩形周长并(线段树、扫描线总结)