Skip to content

S2OJ - 1256. 牧场

题解约 1.1 千字
检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

题面

题目描述

小 L 准备建一个牧场在里面放羊。他指定了一些他想围住的矩形草坪。他想知道把这些草坪围起来需要多长的栏杆。

例如,选取图一的草坪,栏杆将围成图二的样子。

▲ 图 1

▲ 图 2

输入格式

输入文件的第一行是一个整数 nn,表示有多少个矩形。

接下来 nn 行给出了每一个矩形左下角坐标 sx,sys_x,s_y 和右上角坐标 tx,tyt_x,t_y

输出格式

一个正整数,表示所有矩形的周长

输入输出样例

样例输入 #1

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

样例输出 #1

228

数据范围与约定

数据点 nn 特殊性质 时间限制
1 =1= 1 1s
2 =2= 2
3 10\leq 10
4 100\leq 100 0所有坐标10000 \leq \text{\small{所有坐标}} \leq 1000
5 2000\leq 2000
6
7 5000\leq 5000
8 50000\leq 50000 0所有坐标10000 \leq \text{\small{所有坐标}} \leq 1000 1.5s
9
10 200000\leq 200000

对于 100%100\% 的数据,满足 1n2×105, 105sx,sy,tx,ty1051 \leq n \leq 2 \times 10^5, ~ -10^5 \leq s_x, s_y, t_x, t_y \leq 10^5

思路

很容易想到可以在横向和纵向上各使用一次扫描线来计算周长。

可以发现增加一条边后会引起总和改变,总和的改变量就是新增的边长,而没改变的部分则是被已存在图形覆盖掉的,无需统计。

最后将横向上的边长和与纵向上的边长和相加即为图形总周长。

代码

#pragma GCC optimize("Ofast")

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <vector>

const int N = 2e5 + 5;

int n;
long long ans;
std::vector<int> ys;

template <typename T>
void read(T& x) {
    int f = 1;
    char ch = getchar();
    x = 0;
    while (!isdigit(ch)) {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    x *= f;
}

struct segment {
    int x, y1, y2, k;

    segment()
        : x(0), y1(0), y2(0), k(0) {}
    segment(int _x, int _y1, int _y2, int _k)
        : x(_x), y1(_y1), y2(_y2), k(_k) {}

    bool operator<(const segment& b) const {
        return x == b.x ? k > b.k : x < b.x;
    }
} seg[N << 1];

struct rectangle {
    int x1, y1, x2, y2;
} q[N];

struct node {
    int l, r;
    long long cnt, len;

    node()
        : l(0), r(0), cnt(0), len(0) {}
    node(int _l, int _r)
        : l(_l), r(_r), cnt(0), len(0) {}
} tr[N << 3];

inline int find(int y) {
    return std::lower_bound(ys.begin(), ys.end(), y) - ys.begin();
}

inline void pushup(int u) {
    if (tr[u].cnt) {
        tr[u].len = ys[tr[u].r + 1] - ys[tr[u].l];
    } else if (tr[u].l != tr[u].r) {
        tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
    } else {
        tr[u].len = 0;
    }
}

void build(int u, int l, int r) {
    tr[u] = node(l, r);
    if (l == r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
}

void modify(int u, int l, int r, int x) {
    if (l <= tr[u].l && tr[u].r <= r) {
        tr[u].cnt += x;
    } else {
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(u << 1, l, r, x);
        if (r > mid) modify(u << 1 | 1, l, r, x);
    }
    pushup(u);
}

void solve() {
    std::sort(ys.begin(), ys.end());
    std::sort(seg, seg + n * 2);
    ys.erase(std::unique(ys.begin(), ys.end()), ys.end());
    build(1, 0, ys.size() - 2);
    for (int i = 0; i < n * 2; i++) {
        int last = tr[1].len;
        if (seg[i].y1 == seg[i].y2) continue;
        modify(1, find(seg[i].y1), find(seg[i].y2) - 1, seg[i].k);
        ans += abs(tr[1].len - last);
    }
    ys.clear();
}

int main() {
    read(n);
    for (int i = 0; i < n; i++) {
        read(q[i].x1), read(q[i].y1), read(q[i].x2), read(q[i].y2);
    }
    for (int i = 0, j = 0; i < n; i++) {
        seg[j++] = segment(q[i].x1, q[i].y1, q[i].y2, 1);
        seg[j++] = segment(q[i].x2, q[i].y1, q[i].y2, -1);
        ys.push_back(q[i].y1);
        ys.push_back(q[i].y2);
    }
    solve();
    for (int i = 0, j = 0; i < n; i++) {
        seg[j++] = segment(q[i].y1, q[i].x1, q[i].x2, 1);
        seg[j++] = segment(q[i].y2, q[i].x1, q[i].x2, -1);
        ys.push_back(q[i].x1);
        ys.push_back(q[i].x2);
    }
    solve();
    printf("%lld\n", ans);
    return 0;
}