Giả sử chúng ta có một danh sách các hình chữ nhật (căn chỉnh trục). Ở đây mỗi rectangle[i] = {x1, y1, x2, y2}, trong đó (x1, y1) là điểm góc dưới bên trái, và (x2, y2) là điểm góc trên bên phải của hình chữ nhật thứ i.
Chúng ta phải tìm tổng diện tích được bao phủ bởi tất cả các hình chữ nhật trên mặt phẳng. Câu trả lời có thể rất lớn, nên chúng ta có thể sử dụng modulo 10^9 + 7.
Vì vậy, nếu đầu vào giống như
thì đầu ra sẽ là 6.
Để giải quyết bài toán này, chúng ta sẽ làm theo các bước sau −
m = 10^9 + 7
Định nghĩa một hàm add(), nhận vào a, b,
trả về ((a mod m) + (b mod m) mod m)
Định nghĩa một hàm compress nhận ma trận 2D v
Định nghĩa một mảng temp
for khởi tạo i := 0, khi i < kích thước của v, cập nhật (tăng i lên 1), thực hiện −
chèn v[i, 0] vào cuối temp
chèn v[i, 2] vào cuối temp
sắp xếp mảng temp
Định nghĩa một map, ret
idx := 0
for khởi tạo i := 0, khi i < kích thước của temp, cập nhật (tăng i lên 1), thực hiện
nếu temp[i] không phải là thành viên của ret, thì −
ret[temp[i]] := idx
(tăng idx lên 1)
trả về ret
Từ phương thức main thực hiện như sau −
Định nghĩa một mảng xv
chèn { 0 } vào cuối xv
for khởi tạo i := 0, khi i < kích thước của v, cập nhật (tăng i lên 1), thực hiện −
chèn v[i, 0] vào cuối xv
chèn v[i, 2] vào cuối xv
sắp xếp mảng xv
uniItr = phần tử đầu tiên của danh sách với các phần tử duy nhất của xv
xóa uniItr, từ xv
Định nghĩa một map index
idx := 0
for khởi tạo i := 0, khi i < kích thước của xv, cập nhật (tăng i lên 1), thực hiện −
index[xv[i]] := i
Định nghĩa một mảng count có kích thước bằng kích thước của index
Định nghĩa một mảng 2D x
for khởi tạo i := 0, khi i < kích thước của v, cập nhật (tăng i lên 1), thực hiện −
x1 := v[i, 0], y1 := v[i, 1]
x2 := v[i, 2], y2 := v[i, 3]
chèn { y1, x1, x2, 1 } vào cuối x
chèn { y2, x1, x2, -1 } vào cuối x
sắp xếp mảng x
ret := 0
sum := 0, currentY := 0
for khởi tạo i := 0, khi i < kích thước của x, cập nhật (tăng i lên 1), thực hiện −
y := x[i, 0]
x1 := x[i, 1], x2 := x[i, 2]
sig := x[i, 3]
ret := add(ret, (y - currentY) * sum)
currentY := y
for khởi tạo i := index[x1], khi i < index[x2], cập nhật (tăng i lên 1), thực hiện −
count[i] := count[i] + sig
sum := 0
for khởi tạo i := 0, khi i < kích thước của count, cập nhật (tăng i lên 1), thực hiện −
nếu count[i] > 0, thì
sum := sum + (xv[i + 1] - xv[i])
trả về ret mod m
Hãy xem triển khai sau để hiểu rõ hơn −
Ví dụ
#include <bits/stdc++.h> using namespace std; typedef long long int lli; const int m = 1e9 + 7; class Solution { public: lli add(lli a, lli b){ return ((a % m) + (b % m) % m); } map<int, int> compress(vector<vector<int> >& v){ vector<int> temp; for (int i = 0; i < v.size(); i++) { temp.push_back(v[i][0]); temp.push_back(v[i][2]); } sort(temp.begin(), temp.end()); map<int, int> ret; int idx = 0; for (int i = 0; i < temp.size(); i++) { if (!ret.count(temp[i])) { ret[temp[i]] = idx; idx++; } } return ret; } int rectangleArea(vector<vector<int> >& v){ vector<int> xv; xv.push_back({ 0 }); for (int i = 0; i < v.size(); i++) { xv.push_back(v[i][0]); xv.push_back(v[i][2]); } sort(xv.begin(), xv.end()); vector<int>::iterator uniItr = unique(xv.begin(), xv.end()); xv.erase(uniItr, xv.end()); map<int, int> index; int idx = 0; for (int i = 0; i < xv.size(); i++) { index[xv[i]] = i; } vector<int> count(index.size()); vector<vector<int> > x; int x1, x2, y1, y2; for (int i = 0; i < v.size(); i++) { x1 = v[i][0]; y1 = v[i][1]; x2 = v[i][2]; y2 = v[i][3]; x.push_back({ y1, x1, x2, 1 }); x.push_back({ y2, x1, x2, -1 }); } sort(x.begin(), x.end()); lli ret = 0; lli sum = 0, currentY = 0; for (int i = 0; i < x.size(); i++) { lli y = x[i][0]; x1 = x[i][1]; x2 = x[i][2]; int sig = x[i][3]; ret = add(ret, (y - currentY) * sum); currentY = y; for (int i = index[x1]; i < index[x2]; i++) { count[i] += sig; } sum = 0; for (int i = 0; i < count.size(); i++) { if (count[i] > 0) { sum += (xv[i + 1] - xv[i]); } } } return ret % m; } }; main(){ Solution ob; vector<vector<int>> v = {{0,0,2,2},{1,0,2,3},{1,0,3,1}}; cout << (ob.rectangleArea(v)); } Đầu vào
{{0,0,2,2},{1,0,2,3},{1,0,3,1}} Đầu ra
6