CCCPaste

Wex_OA_2

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

// Function to compress and sort coordinate values
vector<int> getCompressedCoords(const set<int>& coords) {
return vector<int>(coords.begin(), coords.end());
}

// Function to calculate total rectangle area
long long calculateRectangleArea(const vector<vector<int>>& rectangles) {
int n = rectangles.size();
set<int> xSet, ySet;

// Step 1: Collect all x and y coordinates
for (const auto& rect : rectangles) {
xSet.insert(rect[0]);
ySet.insert(rect[1]);
xSet.insert(rect[2]);
ySet.insert(rect[3]);
}

// Step 2: Coordinate compression
vector<int> xVals = getCompressedCoords(xSet);
vector<int> yVals = getCompressedCoords(ySet);

// Step 3: Store unique small rectangles (grid cells)
set<vector<int>> activeCells;
for (const auto& rect : rectangles) {
int x1 = lower_bound(xVals.begin(), xVals.end(), rect[0]) - xVals.begin();
int x2 = lower_bound(xVals.begin(), xVals.end(), rect[2]) - xVals.begin();
int y1 = lower_bound(yVals.begin(), yVals.end(), rect[1]) - yVals.begin();
int y2 = lower_bound(yVals.begin(), yVals.end(), rect[3]) - yVals.begin();

for (int i = x1; i < x2; i++) {
for (int j = y1; j < y2; j++) {
activeCells.insert({xVals[i], yVals[j], xVals[i + 1], yVals[j + 1]});
}
}
}

// Step 4: Compute the total area
long long totalArea = 0;
for (const auto& cell : activeCells) {
long long xLen = cell[2] - cell[0];
long long yLen = cell[3] - cell[1];
totalArea = (totalArea + (xLen * yLen) % MOD) % MOD;
}

return totalArea;
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int n;
cout << "Enter number of rectangles: ";
cin >> n;

vector<vector<int>> rectangles(n, vector<int>(4));
cout << "Enter rectangles (x1 y1 x2 y2):\n";
for (int i = 0; i < n; i++) {
cin >> rectangles[i][0] >> rectangles[i][1] >> rectangles[i][2] >> rectangles[i][3];
}

long long result = calculateRectangleArea(rectangles);
cout << "Total Covered Area = " << result << "\n";

return 0;
}