鉄則本 B09 - Papers (2Q, ★4)

二次元いもす法の練習問題

• 問題へのリンク

問題概要

二次元平面上に 枚の長方形の紙がある。 枚目の紙の左下の座標は であり、右上の座標は である。

紙に覆われている部分の面積を求めよ。

制約

• 
• 
• 

考えたこと

二次元いもす法の練習。

github.com

コード

#include <bits/stdc++.h>
using namespace std;
const int MAX = 1600;

int main() {
    int N;
    cin >> N;
    
    // いもす法の準備
    vector num(MAX + 1, vector(MAX + 1, 0));
    for (int i = 0; i < N; ++i) {
        int A, B, C, D;
        cin >> A >> B >> C >> D;
        ++num[A][B], --num[A][D], --num[C][B], ++num[C][D];
    }
    
    // いもす法の累積和
    for (int i = 0; i <= MAX; ++i) {
        for (int j = 0; j < MAX; ++j) num[i][j + 1] += num[i][j];
    }
    for (int j = 0; j <= MAX; ++j) {
        for (int i = 0; i < MAX; ++i) num[i + 1][j] += num[i][j];
    }
    
    // 集計
    int res = 0;
    for (int i = 0; i < MAX; ++i) {
        for (int j = 0; j < MAX; ++j) {
            if (num[i][j]) ++res;
        }
    }
    cout << res << endl;
}