Просмотр кода страницы СГУ 319

== Ссылка на задачу ==
* [http://acm.sgu.ru/problem.php?problem=319 СГУ #319 &mdash; Kalevich Strikes Back]

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

Выполним сжатие координат y &rarr; 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]);
 }

[[Category: Сборник задач: СГУ]]
[[Category: Задачи: Дерево отрезков]]
[[Category: Задачи: Сканирующая прямая]]
[[Category: Задачи: Сжатие координат]]