油漆面积

原题目链接

题目描述

X 星球的一批考古机器人正在一片废墟上考古。

该区域的地面坚硬如石、平整如镜。

为了方便管理人员作业，建立了标准的直角坐标系。

每个机器人都有不同的测量方式和关注点，因此它们报告了若干个矩形区域，作为优先考古的区域。

每个矩形用 (x1, y1, x2, y2) 表示，代表矩形的两个对角点坐标。

总部要求对所有机器人选中的矩形区域涂上黄色油漆，小明的任务是计算这些矩形区域覆盖的总面积。

需要注意的是，各个矩形之间可能存在重叠。

---

输入描述

• 第一行包含一个整数 n，表示有多少个矩形（1 ≤ n ≤ 10⁴）。
• 接下来 n 行，每行包含 4 个整数 x1 y1 x2 y2（0 ≤ x1, y1, x2, y2 ≤ 10⁴），表示矩形的两个对角点。

---

输出描述

输出一个整数，表示所有矩形覆盖的总面积（单位面积）。

---

输入样例

3
1 5 10 10
3 1 20 20
2 7 15 17

---

输出样例

340

c++代码

#include <bits/stdc++.h>
using namespace std;

const int N = 20005;
vector<double> xx(1);

class tree {
public:
    double val = 0;
    int lazy = 0;
};

vector<tree> trees(4 * N);

class ScanLine {
public:
    double y;
    double left_x, right_x;
    int inout;
    ScanLine() {}
    ScanLine(double y, double x1, double x2, int io)
        : y(y), left_x(x1), right_x(x2), inout(io) {}
};
vector<ScanLine> line(1);

bool cmp(ScanLine &a, ScanLine &b) {
    return a.y < b.y;
}

void update(int L, int R, int io, int p, int pl, int pr) {
    if (L <= pl && pr <= R) {
        trees[p].lazy += io;
        if (trees[p].lazy > 0) trees[p].val = xx[pr] - xx[pl];
        else if (pl + 1 == pr) trees[p].val = 0;
        else trees[p].val = trees[2 * p].val + trees[2 * p + 1].val;
        return;
    }
    if (pl + 1 == pr) return;
    int mid = (pl + pr) / 2;
    if (L <= mid) update(L, R, io, 2 * p, pl, mid);
    if (R > mid)  update(L, R, io, 2 * p + 1, mid, pr);
    if (trees[p].lazy > 0) trees[p].val = xx[pr] - xx[pl];
    else if (pl + 1 == pr) trees[p].val = 0;
    else trees[p].val = trees[2 * p].val + trees[2 * p + 1].val;
}

int main() {
    int n;
    scanf("%d", &n);
    while (n--) {
        double x1, x2, y1, y2;
        scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
        line.push_back(ScanLine(y1, x1, x2, 1));
        xx.push_back(x1);
        line.push_back(ScanLine(y2, x1, x2, -1));
        xx.push_back(x2);
    }
    int cnt = line.size() - 1;
    sort(xx.begin() + 1, xx.end());
    xx.erase(unique(xx.begin() + 1, xx.end()), xx.end());
    sort(line.begin() + 1, line.end(), cmp);
    double ans = 0;
    for (int i = 1; i <= cnt; ++i) {
        ans += trees[1].val * (line[i].y - line[i - 1].y);
        int L = lower_bound(xx.begin() + 1, xx.end(), line[i].left_x) - xx.begin();
        int R = lower_bound(xx.begin() + 1, xx.end(), line[i].right_x) - xx.begin();
        update(L, R, line[i].inout, 1, 1, xx.size() - 1);
    }
    printf("%.0lf", ans);
    return 0;
}//by wqs

题目解析

扫描线经典题目