BOJ 5625 : 페스트리

• 문제 링크 : boj.kr/5625
• 난이도 : G3
• 태그 : 기하학, 누적합

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

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

    int n;
    cin >> n;
    int arrX[1000001] = {};
    int arrY[1000001] = {};
    for(int i = 0; i < n; i++) {
        int x1, x2, x3, y1, y2, y3;
        cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
        arrX[min({x1,x2,x3})+1] += 1;
        arrX[max({x1,x2,x3})] -= 1;
        arrY[min({y1,y2,y3})+1] += 1;
        arrY[max({y1,y2,y3})] -= 1;
    }

    for(int i = 1; i < 1000001; i++) {
        arrX[i] += arrX[i-1];
        arrY[i] += arrY[i-1];
    }

    int m;
    cin >> m;
    while(m--) {
        string a, b;
        int c;
        cin >> a >> b >> c;
        if(a[0] == 'x') {
            cout << arrX[c] << "\n";
        }
        else {
            cout << arrY[c] << "\n";
        }
    }

    return 0;
}

---

풀이

변이 x, y축에 평행하고 한 페스트리를 둘러싸는 가장 작은 직사각형을 생각해보자.

페스트리가 잘리는 상황을 상상해보면, 이 직사각형과 페스트리는 문제에서 동일하게 생각할 수 있다.

칼질을 축에 수직으로 하기 때문에 앞에서 구한 직사각형을 각 축에 정사영할 수 있다.

이 경우 x = c를 지나는 선분의 개수를 구하는 문제가 되므로 누적합으로 해결할 수 있다.