Ctrlalt: Новая страница: «== Ссылка на задачу == * [http://acm.sgu.ru/problem.php?problem=319 СГУ #319 — Kalevich Strikes Back] == Комментарии == Так …»

2016-06-15T23:42:36Z

Новая страница: «== Ссылка на задачу == * [http://acm.sgu.ru/problem.php?problem=319 СГУ #319 — Kalevich Strikes Back] == Комментарии == Так …»

Новая страница

== Ссылка на задачу ==
* [http://acm.sgu.ru/problem.php?problem=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]);
}

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

СГУ 319 - История изменений

Ctrlalt: Новая страница: «== Ссылка на задачу == * [http://acm.sgu.ru/problem.php?problem=319 СГУ #319 — Kalevich Strikes Back] == Комментарии == Так …»