今日の問題はこちら。
Diffは599(茶)です。
昨日の記事で扱った問題よりは楽な問題です。
提出コードと考え方
「白い長方形が黒で塗られていき、操作終了後の白い部分の面積を求める」と言われると、塗られた黒い部分の面積を求めておいて \(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;
}
コメント