СГУ 319

Ссылка на задачу

• СГУ #319 — Kalevich Strikes Back

Комментарии

Так как прямоугольники не имеют общих точек, они могут лишь целиком располагаться один внутри другого.

Выполним сжатие координат y → y'. Создадим дерево отрезков с запросом элемента и присвоением на отрезке.

Каждый прямоугольник (включая рамку картины) создаёт два события в координатах xl и xr:

• В координате xl прямоугольник начинается. При помощи дерева отрезков определяется внешний прямоугольник (его индекс присвоен элементу yl' - 1), площадь внешнего прямоугольника уменьшается на площадь текущего прямоугольника. После этого отрезку (yl'; yr' - 1) присваивается индекс текущего прямоугольника.

• В координате xr прямоугольник заканчивается. При помощи дерева отрезков определяется внешний прямоугольник (его индекс присвоен элементу yl' - 1), отрезку (yl'; yr' - 1) присваивается индекс внешнего прямоугольника.

Осталось отсортировать и вывести площади.

Код решения

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

class CoordinateCompressor {
    map<int, int> m;
    vector<int> v;
public:
    void add(int x) {
        m[x] = 0;
    }
    void build() {
        for (map<int, int>::iterator i = m.begin(); i != m.end(); i++) {
            i->second = v.size();
            v.push_back(i->first);
        }
    }
    int compress(int x) {
        return m[x];
    }
    int decompress(int x) {
        return v[x];
    }
    int count() {
        return m.size();
    }
} compressor;

class SegmentTree {
    int size;
    vector<int> t;
    int query(int v, int vl, int vr, int pos) {
        if (t[v] != -1 || vl == vr)
            return t[v];
        int vm = vl + (vr - vl) / 2;
        if (pos <= vm)
            return query(2 * v + 1, vl, vm, pos);
        else
            return query(2 * v + 2, vm + 1, vr, pos);
    }
    void modify(int v, int vl, int vr, int l, int r, int val) {
        if (r < vl || vr < l)
            return;
        if (l <= vl && vr <= r) {
            t[v] = val;
            return;
        }
        if (t[v] != -1) {
            t[2 * v + 1] = t[v];
            t[2 * v + 2] = t[v];
            t[v] = -1;
        }
        int vm = vl + (vr - vl) / 2;
        modify(2 * v + 1, vl, vm, l, r, val);
        modify(2 * v + 2, vm + 1, vr, l, r, val);
    }
public:
    SegmentTree() {}
    SegmentTree(int _size) {
        size = _size;
        t = vector<int>(4 * size, -1);
    }
    int query(int pos) {
        if (pos < 0 || pos > size - 1)
            return -1;
        return query(0, 0, size - 1, pos);
    }
    void modify(int l, int r, int val) {
        modify(0, 0, size - 1, l, r, val);
    }
} segmentTree;

struct Rectangle {
    int xl, yl, xr, yr;
    Rectangle(int x1, int y1, int x2, int y2) {
        xl = min(x1, x2);
        xr = max(x1, x2);
        yl = min(y1, y2);
        yr = max(y1, y2);
    }
    long long area() {
        return ((long long)xr - xl) * (yr - yl);
    }
};
vector<Rectangle> rectangles;

long long area[100010];

struct Event {
    int x, index;
    Event(int _x, int _index) {
        x = _x;
        index = _index;
    }
    bool operator < (const Event &that) const {
        return x < that.x;
    }
    void process() {
        int cyl = compressor.compress(rectangles[index].yl);
        int cyr = compressor.compress(rectangles[index].yr);
        int parent = segmentTree.query(cyl - 1);
        if (x == rectangles[index].xl) {
            if (parent != -1)
                area[parent] -= rectangles[index].area();
            area[index] = rectangles[index].area();
            segmentTree.modify(cyl, cyr - 1, index);
        } else {
            if (parent != -1)
                segmentTree.modify(cyl, cyr - 1, parent);
        }
    }
};
vector<Event> events;

int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    int n, w, h;
    scanf("%d%d%d", &n, &w, &h);
    compressor.add(0);
    compressor.add(h);
    rectangles.push_back(Rectangle(0, 0, w, h));

    for (int i = 0; i < n; i++) {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        compressor.add(y1);
        compressor.add(y2);
        rectangles.push_back(Rectangle(x1, y1, x2, y2));
    }

    compressor.build();
    segmentTree = SegmentTree(compressor.count());

    for (int i = 0; i < rectangles.size(); i++) {
        events.push_back(Event(rectangles[i].xl, i));
        events.push_back(Event(rectangles[i].xr, i));
    }
    sort(events.begin(), events.end());
    for (int i = 0; i < events.size(); i++) {
        events[i].process();
    }

    sort(area, area + n + 1);
    for (int i = 0; i < n + 1; i++)
        printf("%lld ", area[i]);
}