BOJ 14411 - 합집합 링크
(2023.06.13 기준 G4)

문제

중심은 원점이며 너비와 넓이가 짝수인 직사각형이 직교좌표계 상에 N개가 주어진다.
모든 직사각형의 합집합의 면적 출력

알고리즘

모든 직사각형간 포함관계를 알아야 한다. 이는 정렬로 판별할 수 있다.

풀이

이런 직사각형이 있다고 생각하자.
먼저 끝점(주어지는 너비 x, 높이 y라고 생각하도 무방하다)을 기준으로 오름차순으로 정렬하여 역순으로 훑자. 그리고 지금까지 훑은 y 좌표 중 최고점을 Y라고 하자. 첫 Y는 0이다.

1. 빨강

• 전에 들어온 사각형이 없으므로 그대로 넓이를 구해 결과에 더하자. 그리고 y를 Y에 저장하자.

2. 주황

• y가 Y보다 작다. x는 내림차순이므로 주황의 면적은 이미 포함되어 있다.

3. 파랑

• y가 Y보다 크다. 파랑의 y 좌표 기준 밑으로는 이미 포함된 면적이므로 윗부분만 넓이를 구해 결과에 더하자. 그리고 y를 Y에 저장하자.

4. 초록

• y가 Y보다 작다. 초록의 면적은 이미 포함되어 있다.
  
  

그리고 한 사분면을 기준으로 구했지만 너비, 높이 기준으로 넓이를 구해 결과를 저장하자.
(x/2)*(y/2)*4 = (x*y/4)*4 = x*y

코드

• C++

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

typedef long long ll;
typedef pair<int, int> pii;

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

    int N; cin >> N;
    vector<pii> pos;
    for (int i = 0, x, y; i < N; i++) cin >> x >> y, pos.push_back({x, y});

    // 오름차순의 역순으로 정렬
    sort(pos.begin(), pos.end()); reverse(pos.begin(), pos.end());

    ll result = 0; int Y = 0; // 넓이 합, 현재 훑은 y 좌표 중 최고점
    for (auto [x, y]: pos)
        if (y > Y){ // y 좌표가 최고점보다 크면 포함되지 않은 면적이 생긴다.
            result += (ll)x * (y - Y); // 포함되지 않은 면적만큼 넓이를 구해 결과에 더하고
            Y = y; // 최고점을 갱신하자.
        }
    cout << result;
}

• Python

import sys; input = sys.stdin.readline

N = int(input())
pos = [tuple(map(int, input().split())) for _ in range(N)]

# 오름차순의 역순으로 정렬
pos.sort(reverse = True)

result = Y = 0 # 넓이 합, 현재 훑은 y 좌표 중 최고점
for x, y in pos:
    if y > Y: # y 좌표가 최고점보다 크면 포함되지 않은 면적이 생긴다.
        result += x * (y - Y) # 포함되지 않은 면적만큼 넓이를 구해 결과에 더하고
        Y = y # 최고점을 갱신하자.
print(result)