Нужно решить на с++

Question

Нужно решить на с++

Александр Феткуллин Ученик (237), на голосовании 5 месяцев назад

Дано N прямоугольников со сторонами, параллельными осям координат. Требуется определить площадь фигуры, образованной объединением данных прямоугольников.
Входные данные
В первой строке входного файла INPUT.TXT находится число прямоугольников - N. Затем идут N строк, содержащих по 4 числа: x1, y1, x2, y2 - координаты двух противоположных углов прямоугольника. Все координаты – целые числа, не превосходящие по абсолютной величине 10 000. (1 <= N <= 100)
Выходные данные
В выходной файл OUTPUT.TXT выведите одно целое число – площадь фигуры.

Нужно решить методом сжатия координат. Код для сжатия координат:
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<int> b = a;
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());
for (int &x: a) {
x = int(lower_bound(b.begin(), b.end(), x) - b.begin());
}

Answer 1

Артём Профи (822) 6 месяцев назад

мне лень

Answer 2

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
int n;
cin >> n;

vector<int> x_coords, y_coords;
for (int i = 0; i < n; i++) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
x_coords.push_back(x1);
x_coords.push_back(x2);
y_coords.push_back(y1);
y_coords.push_back(y2);
}

// Сжатие координат
vector<int> compressed_x = x_coords;
vector<int> compressed_y = y_coords;
sort(compressed_x.begin(), compressed_x.end());
sort(compressed_y.begin(), compressed_y.end());
compressed_x.erase(unique(compressed_x.begin(), compressed_x.end()), compressed_x.end());
compressed_y.erase(unique(compressed_y.begin(), compressed_y.end()), compressed_y.end());

for (int &x : x_coords) {
x = int(lower_bound(compressed_x.begin(), compressed_x.end(), x) - compressed_x.begin());
}
for (int &y : y_coords) {
y = int(lower_bound(compressed_y.begin(), compressed_y.end(), y) - compressed_y.begin());
}

// Построение сетки и вычисление площади
int grid_size_x = compressed_x.size();
int grid_size_y = compressed_y.size();
vector<vector<bool>> grid(grid_size_x, vector<bool>(grid_size_y, false));

for (int i = 0; i < n; i++) {
for (int x = x_coords[2 * i]; x < x_coords[2 * i + 1]; x++) {
for (int y = y_coords[2 * i]; y < y_coords[2 * i + 1]; y++) {
grid[x][y] = true;
}
}
}

long long area = 0;
for (int x = 0; x < grid_size_x - 1; x++) {
for (int y = 0; y < grid_size_y - 1; y++) {
if (grid[x][y]) {
area += (long long)(compressed_x[x + 1] - compressed_x[x]) * (compressed_y[y + 1] - compressed_y[y]);
}
}
}

cout << area << endl;

return 0;
}