สมมติว่าเรามีรายการของสี่เหลี่ยมผืนผ้า (axis-aligned) ที่นี่แต่ละ rectangle[i] = {x1, y1, x2, y2} โดยที่ (x1, y1) คือจุดมุมล่างซ้าย และ (x2, y2) คือจุดมุมบนขวาของสี่เหลี่ยมผืนผ้าลำดับที่ i
เราต้องหาพื้นที่รวมที่ถูกครอบคลุมโดยสี่เหลี่ยมผืนผ้าทั้งหมดในระนาบ คำตอบอาจใหญ่มาก จึงสามารถใช้โมดูล로 10^9 + 7
เช่น หากอินพุตเป็นดังภาพ
เอาต์พุตจะเป็น 6
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนต่อไปนี้ −
m = 10^9 + 7
กำหนดฟังก์ชัน add() รับ a, b คืนค่า ((a mod m) + (b mod m) mod m)
กำหนดฟังก์ชัน compress() รับเมทริกซ์ 2D v
สร้างอาร์เรย์ temp
วนลูป i := 0 ถึง size of v ทำ − เพิ่ม v[i, 0] และ v[i, 2] เข้า temp
เรียงลำดับอาร์เรย์ temp
สร้างแมป ret, idx := 0
วนลูป i := 0 ถึง size of temp ถ้า temp[i] ไม่อยู่ใน ret ให้ ret[temp[i]] := idx และเพิ่ม idx
คืนค่า ret
จากเมธอดหลัก ทำดังนี้ −
สร้างอาร์เรย์ xv เพิ่ม {0} เข้าไป
วนลูป i := 0 ถึง size of v เพิ่ม v[i, 0] และ v[i, 2] เข้า xv
เรียงลำดับ xv, ลบค่าซ้ำด้วย unique
สร้างแมป index, idx := 0 วนลูปกำหนด index[xv[i]] := i
สร้างอาร์เรย์ count ขนาดเท่า index, อาร์เรย์ 2D x
วนลูป i := 0 ถึง size of v ดึง x1, y1, x2, y2 เพิ่ม {y1, x1, x2, 1} และ {y2, x1, x2, -1} เข้า x
เรียงลำดับ x
ret := 0, sum := 0, currentY := 0
วนลูป i := 0 ถึง size of x คำนวณพื้นที่โดยใช้ sweep line algorithm
คืนค่า ret mod m
ลองดูการนำไปใช้ต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น −
ตัวอย่าง
#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));
}
อินพุต
{{0,0,2,2},{1,0,2,3},{1,0,3,1}}
เอาต์พุต
6
