백준 7626 (C++) 직사각형

최초 업로드: 2025-04-23 07:03:48

최근 수정 시간: 2025-07-25 09:11:03

게시자: rlatjwls3333

카테고리: 백준

# [Platinum I] 직사각형

#### [문제 링크](https://www.acmicpc.net/problem/7626)

## 문제 설명

축에 평행한 직사각형 N개가 평면 위에 있다. 이 직사각형들이 차지하는 전체 면적을 구하는 프로그램을 작성하시오.

## 입력

첫째 줄에 양의 정수 N이 주어진다. (1 ≤ N ≤ 200,000) 다음 N개 줄에는 공백으로 나누어진 네 값 "x1, x2, y1, y2"가 주어진다. 이 값은 직사각형 [x1,x2] × [y1,y2]를 나타낸다. 모든 좌표는 0보다 크거나 같고, 109보다 작거나 같으며, 각각의 직사각형은 x1 < x2, y1 < y2를 만족한다.

## 출력

첫째 줄에 주어진 직사각형 N개가 차지하는 전체 면적을 출력한다. 한 구역이 여러 개의 직사각형으로 덮어져 있는 경우에도 한 번으로 센다.

## 풀이
#### x를 기준으로 정렬하고 스위핑하면서 현재 활성화된 y범위를 계산하여 넓이를 구하면 된다. y범위가 크기에 좌표 압축을 한 후 세그먼트 트리로 최적화를 해야 한다.

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

const int MAX = 400000;

struct pos {
    int x, y1, y2, val;
};

int n;
vector<pos> v;
vector<int> yList;
int _size, yLen[MAX*4], arr[MAX*4], cnt[MAX*4];

void construct() {
 cin >> n;
 for(int i=0;i<n;i++) {
 int x1, x2, y1, y2; cin >> x1 >> x2 >> y1 >> y2;
 v.push_back({x1, y1, y2, 1});
 v.push_back({x2, y1, y2, -1});
 yList.push_back(y1);
 yList.push_back(y2);
 }
 yList.erase(unique(yList.begin(), yList.end()), yList.end());
 sort(yList.begin(), yList.end());
 sort(v.begin(), v.end(), [](pos a, pos b){ return a.x < b.x; });

_size=1;
 while(_size<MAX) _size<<=1;
 _size<<=1;
 for(int i=1;i<yList.size();i++) yLen[i-1+_size/2] = yList[i]-yList[i-1];
 for(int i=_size/2-1;i>0;i--) yLen[i] = yLen[i*2] + yLen[i*2+1];
}

void updateRange(int L, int R, int nodeNum, int nodeL, int nodeR, int val) {
 if(R<nodeL || nodeR<L) return;
 if(L<=nodeL && nodeR<=R) {
 cnt[nodeNum] += val;
 } else {
 int mid = (nodeL+nodeR)/2;
 updateRange(L, R, nodeNum*2, nodeL, mid, val);
 updateRange(L, R, nodeNum*2+1, mid+1, nodeR, val);
 }
 if(cnt[nodeNum]) arr[nodeNum] = yLen[nodeNum];
 else if(nodeL==nodeR) arr[nodeNum] = 0;
 else arr[nodeNum] = arr[nodeNum*2] + arr[nodeNum*2+1];
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    construct();

long long total=0, last=0;
 for(pos p : v) {
 p.y1 = lower_bound(yList.begin(), yList.end(), p.y1) - yList.begin();
 p.y2 = lower_bound(yList.begin(), yList.end(), p.y2) - yList.begin();
 total += (p.x-last)*arr[1];
 updateRange(p.y1, p.y2-1, 1, 0, _size/2-1, p.val);
 last = p.x;
 }
 cout << total;
}
```