Skip to content

S2OJ - 1256. 牧场

题解约 1.1 千字
# S2OJ # 线段树 # 2018 # 常中集训 # 扫描线
检测到 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\% 的数据，满足 1≤n≤2×105, −105≤sx,sy,tx,ty≤1051 \leq n \leq 2 \times 10^5, ~ -10^5 \leq s_x, s_y, t_x, t_y \leq 10^5。

#思路

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

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

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

#代码

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#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;
}