【競プロ】1日1AC : ABC47 B問題 すぬけ君の塗り絵 2 イージー

今日の問題はこちら。

Diffは599（茶）です。

昨日の記事で扱った問題よりは楽な問題です。

【競プロ】1日1AC : ABC138 D問題 Ki

2020年4月22日

【競プロ】累積和を覚える

2020年4月22日

提出コードと考え方

「白い長方形が黒で塗られていき、操作終了後の白い部分の面積を求める」と言われると、塗られた黒い部分の面積を求めておいて \(W\times H\) から引いて求めたくなります。

しかし、黒い部分が重複することがあり面倒です。

問題文の設定では、

• \(a_i=1\) のとき \(x_i\) より左を黒く塗る
• \(a_i=2\) のとき \(x_i\) より右を黒く塗る
• \(a_i=3\) のとき \(y_i\) より下を黒く塗る
• \(a_i=4\) のとき \(y_i\) より上を黒く塗る

となっていますが、白い部分を確定させていくようにしましょう。

つまり、

• \(a_i=1\) のとき \(x_i\) より右を選択する
• \(a_i=2\) のとき \(x_i\) より左を選択する
• \(a_i=3\) のとき \(y_i\) より上を選択する
• \(a_i=4\) のとき \(y_i\) より下を選択する

と考え、指定される範囲の共通部分を取ることで、白い長方形の辺の長さの情報を得られます。（共通部分がなければ面積は \(0\)）

実装では上下左右の辺の位置を変数として持ち、値を更新していきます。

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;

int main(){
    int w,h,n;
    cin >> w >> h >> n;
    int x,y,a;
    int left = 0;
    int right = w;
    int up = h;
    int bottom = 0;
    rep(i,n){
        cin >> x >> y >> a;
        // left, bottomは大きいものをとる
        // right,upは小さいものをとる
        if(a == 1) left = max(left,x);
        if(a == 2) right = min(right,x);
        if(a == 3) bottom = max(bottom,y);
        if(a == 4) up = min(up,y);
    }
    if(left >= right || up <= bottom) cout << 0 << endl;
    else cout << (right-left)*(up-bottom) << endl;
    return 0;
}