IT教程 ·

一文大概看懂扫描线

曹工说Spring Boot源码(19)-- Spring 带给我们的工具利器,创建代理不用愁(ProxyFactory)

扫描线入门

本文的笔墨部份有些冗杂,有些处所讲的也有些死板,然则笔者已只管让笔墨不那末艰涩,也加了一些配图,置信对峙看完的读者会有所收成
本文参考:

矩形面积并

关于矩形(A,B),它们的面积并就是(A cup B)的面积,多个矩形的状况能够类比一下。怎样求面积并呢?有一种主意是拿一切矩形面积之和减去多加了的部份的面积,然则多加的部份并不好求,由于要盘算交点,还要晓得反复部份究竟反复了若干次;我们能够设想有一条与(x)轴平行的直线,从下往上扫,把面积并分割成多个部份,如下图所示,如许以来面积并就即是各个色彩的部份的面积之和,每一个部份的高很轻易求,只要把每一个矩形的每一个横向边(与(x)轴平行的边)的高度纪录一下,排个序,做差就可以够,关键在于怎样求每一个部份的长度,这时刻,线段树又进场了(不晓得线段树的话,这里是)

一文大概看懂扫描线 IT教程 第1张

图片地点:

区间信息

既然要用线段树,那线段树存什么?或者说要保护区间信息是什么?我们对横坐标区间建线段树,根节点的区间是([x_{min}, x_{max}])((x)是(double)咋整?能够离散化,下面会讲),即最左端的横坐标到最右端的横坐标,区间信息就是区间内有用的横向长度,如许每次拿高乘×根节点存的有用横向长度就可以算出每一个部份的面积,再累加就是答案了;那末要怎样保护区间信息呢?我们给每一个区间保护一个(cnt),即如今该区间被横边掩盖的次数,怎样看这个如今呢?假如插进去的是矩形下边境的横边,那被掩盖次数加一;相反,假如是上边境被掩盖次数减一。如许假如一个区间的(cnt > 0),申明该区间已被完整掩盖了,那有用长度就即是区间长度;不然,假如(cnt == 0)((cnt)不会小于0,除非你把下边境标记成上边境,上边境标记成下边境),那该区间的有用长度就是它的左儿子的有用长度加右儿子的(假如是叶子节点有用长度就是0),咱用下面的图模仿一下:

在这之前咱先讲讲,用到的构造体和数组定义,如许轻易下文议论。我们定义一个构造体(Seg)来示意矩形的高低边境(即横向边)以及构造体(Node)来示意线段树的各个节点;定义(double)数组(corx)存横坐标

const int N = 205; // 点数,即横向边的数目的两倍

struct Seg {
    double l, r, h; // 左端点右端点和高度
    int d; // 下边境的d==1,上边境的d==-1,你品,你细品
    Seg() {}
    Seg(double l, double r, double h, int d) : l(l), r(r), h(h), d(d) {}
    inline bool operator < (const Seg& a) { // 用于将高低边境依据高度排序
        return h < a.h;
    }
} seg[N];

struct Node {
    int l, r, cnt; // l和r要用到离散化技能,以后会讲,cnt区间就是被掩盖次数
    double sum; // 有用长度
} node[N << 2];

double corx[N];

(事前(seg)数组已依据(h)排序)起首,对区间([x_1, x_4])建线段树(这里的(x)坐标没排序),扫描线从(h1)入手下手,碰到第一个下边境(x3x4),并将它插进去到线段树中,这时刻第一部份(下图灰色部份)的面积就即是(node[1].sum*(seg[2].h - seg[1].h));然后,扫描线抵达(h2),插进去(x1x2),蓝色部份面积即是(node[1].sum * (seg[3].h - seg[2].h)),(h3)相似,到(h4)时,由于它是上边境,它会将([x3,x4])部份的(cnt)值减1,然后盘算赤色部份面积,然后一步步算出总面积

一文大概看懂扫描线 IT教程 第2张

离散化

为啥要离散?

有两点缘由:

  • 有些题目给的坐标局限大概很大,比方(1e9),开数组必爆无疑
  • 坐标大概照样(double),如许线段树不太好竖立,设想一下区间端点是(double)型的线段树的叶子是个啥(横竖以笔者的程度是捣鼓不出来的)

怎样离散

我们能够不拿横坐标的值来当区间,而拿横坐标是从左往右的第几个来当区间,看图

如许线段树的根节点的区间就缩小到([1,N])了,能够存得下了,下面问题又来了,插进去时怎样插?之前区间端点直接插进去就得了,如今离散了咋整?由于我们已对横坐标们排序,那我们用每条(seg)的摆布端点的值经由过程(lowerbound)就可以找到其在(corx)中对应的下标,这下就可以疾速插进去了

亿点细节

心急的同砚大概早就去看板子了(由于人人都会了),但是大概会有一些看不懂的新鲜细节:

  • 上文说道假如一个区间的(cnt>0),那该区间的有用长度就是区间长度,然则如今离散化了,不能直接区间长度了,应当是坐标值之差
  • 为啥板子71行(x)不减1,(y)减1?为啥(update)里(node[k].r)要加1,而(node[k].l)不加1?明显这两者是相互对应的,以下是笔者本身的看法,大概有毛病,仅供参考:我们能够考虑一下,线段树的叶子节点,比方(node[k].l == node[k].r == 1)时,它的区间信息(sum)究竟代表着什么,它应当代表的是从1入手下手,长度为1单元长度的区间内被掩盖的状况,那末从叶子节点向上,(node[k'])的区间信息(sum)代表的是从端点(l)入手下手,到端点(r)后,再往右1单元长度的如许区间的有用长度,所以(y)要减1,不然插进去的区间就变成了([x, y + 1])了;而(update)函数中的(node[k].r + 1)也诠释得清晰了,然则读者们又要问了:那(update)里的(else if)那一行不该当是(node[k].sum = 1)吗?毕竟叶子节点代表的区间长度是1啊!叶子节点的区间长度确切是1,然则我们看上一句(if)的前提,只要在(cnt == 0)时,才有大概实行(else if)的语句,也就是说这时刻该区间的被掩盖次数为0,天然(sum=0)而不是(1),初始化的时刻也一样,区间被掩盖次数为(0),天然(sum = 0)
void update(int k) {
    if(node[k].cnt) node[k].sum = corx[node[k].r + 1] - corx[node[k].l]; // 区间被完整掩盖
    else if(node[k].l == node[k].r) node[k].sum = 0; // 叶子
    else node[k].sum = node[ls].sum + node[rs].sum;
}

71行:x = std::lower_bound(corx + 1, corx + sz + 1, seg[i].l) - corx;
              y = std::lower_bound(corx + 1, corx + sz + 1, seg[i].r) - corx - 1;

照笔者这么说的话,线段树区间([1, N-1])就够了,在HDU上确切也(AC)了(只测了下面的板子题),但是并不能说笔者的说法是准确的,所以照样建([1, N])的树吧,毕竟仅仅测试了无数测试数据中的寥寥几组,仅作为一个参考

板子

#include <cstdio>
#include <algorithm>
#define ls (k << 1)
#define rs (ls | 1)
const int N = 205;

struct Seg {
    double l, r, h;
    int d;
    Seg() {}
    Seg(double l, double r, double h, int d) : l(l), r(r), h(h), d(d) {}
    bool operator < (const Seg &a) const {
        return h < a.h;
    }
}seg[N];

struct Node {
    int l, r, cnt;
    double sum;
}node[N << 2];

int n, x, y, d;
double corx[N];

void build(int l, int r, int k) {
    node[k].l = l; node[k].r = r; node[k].cnt = node[k].sum = 0;
    if(l == r) return ;
    int mid = (l + r) >> 1;
    build(l, mid, ls);
    build(mid + 1, r, rs);
}

void update(int k) {
    if(node[k].cnt) node[k].sum = corx[node[k].r + 1] - corx[node[k].l]; // 区间被完整掩盖
    else if(node[k].l == node[k].r) node[k].sum = 0; // 叶子
    else node[k].sum = node[ls].sum + node[rs].sum;
}

void work(int k) {
    if(node[k].l >= x && node[k].r <= y) {
        node[k].cnt += d;
        update(k);
        return ;
    }
    int mid = (node[k].l + node[k].r) >> 1;
    if(x <= mid) work(ls);
    if(y > mid) work(rs);
    update(k);
}

int main() {
    int kase = 0;
    while(~scanf("%d", &n)) {
        if(!n) break;
        for(int i = 1; i <= n; i++) {
            double x1, x2, y1, y2;
            scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
            corx[i] = x1; corx[n + i] = x2;
            seg[i] = Seg(x1, x2, y1, 1);
            seg[i + n] = Seg(x1, x2, y2, -1);
        }
        n <<= 1;
        std::sort(corx + 1, corx + n + 1);
        std::sort(seg + 1, seg + n + 1);
        int sz = std::unique(corx + 1, corx + n + 1) - corx - 1; // 去重
        double ans = 0;
        build(1, sz, 1);
        for(int i = 1; i < n; i++) {
            x = std::lower_bound(corx + 1, corx + sz + 1, seg[i].l) - corx;
            y = std::lower_bound(corx + 1, corx + sz + 1, seg[i].r) - corx - 1;
            d = seg[i].d;
            work(1);
            ans += (seg[i + 1].h - seg[i].h) * node[1].sum;
        }
        printf("Test case #%dnTotal explored area: %.2fnn", ++kase, ans);
    }
    return 0;
}

例题

  • 这题是求矩形并后的图形的周长,也是扫描线,以后特地再发一篇讲怎样算周长吧

临时还没做若干例题(就是没做,以后再补点题,咕咕)

优雅地使用 C++ 制作表格:tabulate

参与评论