矩形周长(Picture) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;

struct Event {
    int x, y1, y2, type;
    bool operator<(const Event& o) const {
        if (x != o.x) return x < o.x;
        return type > o.type; // +1 before -1 on collinear edges!
    }
};

const int OFFSET = 10000;
const int MAXC = 20000;

struct SegTree {
    vector<int> cnt, len;
    SegTree() : cnt(4 * MAXC + 5, 0), len(4 * MAXC + 5, 0) {}
    void pull(int node, int l, int r) {
        if (cnt[node] > 0) len[node] = r - l;
        else if (l + 1 == r) len[node] = 0;
        else len[node] = len[node << 1] + len[node << 1 | 1];
    }
    void update(int node, int l, int r, int ql, int qr, int v) {
        if (ql <= l && r <= qr) {
            cnt[node] += v;
            pull(node, l, r);
            return;
        }
        int mid = (l + r) >> 1;
        if (ql < mid) update(node << 1, l, mid, ql, qr, v);
        if (qr > mid) update(node << 1 | 1, mid, r, ql, qr, v);
        pull(node, l, r);
    }
};

long long sweep(vector<Event>& ev) {
    sort(ev.begin(), ev.end());
    SegTree st;
    long long res = 0;
    int last_len = 0;
    for (const auto& e : ev) {
        if (e.y1 < e.y2) {
            st.update(1, 0, MAXC, e.y1 + OFFSET, e.y2 + OFFSET, e.type);
        }
        res += abs(st.len[1] - last_len);
        last_len = st.len[1];
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<Event> ev_x, ev_y;
    for (int i = 0; i < n; ++i) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if (x1 > x2) swap(x1, x2);
        if (y1 > y2) swap(y1, y2);
        ev_x.push_back({x1, y1, y2, 1});
        ev_x.push_back({x2, y1, y2, -1});
        ev_y.push_back({y1, x1, x2, 1});
        ev_y.push_back({y2, x1, x2, -1});
    }
    cout << (sweep(ev_x) + sweep(ev_y)) << "\n";
    return 0;
}