C++(clang++11) 解法, 执行用时: 540ms, 内存消耗: 608K, 提交时间: 2021-03-24 02:09:21

#include <bits/stdc++.h>

using namespace std;

const int N = 1e4 + 5;
typedef long long LL;

int n;
struct node {
    int x, y, d;
} a[N];
LL sqr(LL x) { return x < 0ll ? 0ll : x * x; }
bool cmpy(node a, node b) { return a.y < b.y; }
vector<int> ys;
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i].x >> a[i].y >> a[i].d;
        if (a[i].d == 0) continue;
        ys.push_back(a[i].x), ys.push_back(a[i].x + a[i].d);
    }
    sort(a, a + n, cmpy);
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    LL res = 0;
    for (int i = 1; i < ys.size(); i++) {
        int dn = 0, up = 0;  // upl
        for (int j = 0; j < n; j++) {
            if (a[j].d == 0) continue;
            if (a[j].x <= ys[i - 1] && a[j].x + a[j].d >= ys[i]) {
                if (dn == 0 && up == 0) {
                    dn = a[j].y;
                    up = a[j].y + a[j].d - (ys[i - 1] - a[j].x);
                } else {
                    if (a[j].y > up) {
                        res += 2ll * (up - dn) * (ys[i] - ys[i - 1]) -
                               sqr(ys[i] - ys[i - 1]);
                        dn = a[j].y;
                        up = a[j].y + a[j].d - (ys[i - 1] - a[j].x);
                    } else if (a[j].y + a[j].d - (ys[i - 1] - a[j].x) > up) {
                        res += 2ll * (ys[i] - ys[i - 1]) * (a[j].y - dn);
                        if (a[j].y > up - (ys[i] - ys[i - 1])) {
                            res -= sqr(a[j].y - (up - (ys[i] - ys[i - 1])));
                        }
                        dn = a[j].y;
                        up = a[j].y + a[j].d - (ys[i - 1] - a[j].x);
                    }
                }
            }
        }
        if (up == 0 && dn == 0)
            continue;
        else {
            res +=
                2ll * (up - dn) * (ys[i] - ys[i - 1]) - sqr(ys[i] - ys[i - 1]);
        }
    }
    printf("%.1lf", res / 2.0);
    return 0;
}