(축 정렬) 직사각형 목록이 있다고 가정합니다. 여기서 각 직사각형[i] ={x1, y1, x2, y2}, 여기서 (x1, y1)은 왼쪽 아래 모서리의 점이고 (x2, y2)는 오른쪽 위 모서리의 점입니다. i번째 직사각형.
평면의 모든 직사각형이 차지하는 전체 면적을 찾아야 합니다. 답은 매우 이므로 모듈로 10^9 + 7을 사용할 수 있습니다.
따라서 입력이 다음과 같으면
그러면 출력은 6이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
m =10^9 + 7
-
add() 함수를 정의하면, b,
-
return ((a mod m) + (b mod m) mod m)
-
하나의 함수 압축을 정의하면 2차원 행렬 v
가 사용됩니다. -
어레이 온도 정의
-
initialize i :=0의 경우 i
-
temp
끝에 v[i, 0] 삽입 -
temp
끝에 v[i, 2] 삽입
-
-
배열 온도 정렬
-
하나의 지도 정의, ret
-
아이디:=0
-
for initialize i :=0, i
-
temp[i]가 ret의 멤버가 아니면 -
-
ret[temp[i]] :=idx
-
(idx를 1씩 증가)
-
-
-
리턴 렛
-
주요 방법에서 다음을 수행하십시오 -
-
배열 xv 정의
-
xv의 끝에 { 0 } 삽입
-
initialize i :=0의 경우 i
-
xv의 끝에 v[i, 0] 삽입
-
xv의 끝에 v[i, 2] 삽입
-
-
xv 배열 정렬
-
uniItr =xv의 고유한 요소가 있는 목록의 첫 번째 요소
-
xv에서 uniItr 삭제
-
하나의 지도 색인 정의
-
아이디:=0
-
initialize i :=0의 경우, i
-
인덱스[xv[i]] :=i
-
-
인덱스 크기와 동일한 크기의 배열 개수 정의
-
하나의 2D 배열 정의 x
-
initialize i :=0의 경우 i
-
x1 :=v[i, 0], y1 :=v[i, 1]
-
x2 :=v[i, 2], y2 :=v[i, 3]
-
x의 끝에 { y1, x1, x2, 1} 삽입
-
x의 끝에 { y2, x1, x2, -1 } 삽입
-
-
배열 x
정렬 -
ret :=0
-
합계 :=0, 현재Y :=0
-
initialize i :=0의 경우, i
-
y :=x[i, 0]
-
x1 :=x[i, 1], x2 :=x[i, 2]
-
시그 :=x[i, 3]
-
ret :=add(ret, (y - 현재Y) * 합계)
-
현재Y :=y
-
initialize i :=index[x1]의 경우, i
-
count[i] :=count[i] + 서명
-
-
합계 :=0
-
initialize i :=0의 경우, i <카운트 크기, 업데이트(i를 1만큼 증가)일 때 -
를 수행합니다.-
count[i]> 0이면
-
합계 :=합계 + (xv[i + 1] - xv[i])
-
-
-
-
리턴 모드 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