AtCoderログ：0069 - ABC 047 B

問題

問題文

$xy$ 平面上に、左下の座標が $(0,0)$、右上の座標が $(W,H)$ で、各辺が $x$ 軸か $y$ 軸に平行な長方形があります。最初、長方形の内部は白く塗られています。
すぬけ君はこの長方形の中に $N$ 個の点を打ちました。$i$ 個目 $(1 \le
i \le N)$ 点の座標は $(x_i,y_i)$ でした。
また、すぬけ君は長さ $N$ の数列 $a$ を決めて、各 $1 \le i \le N$ に対し、
・$a_i=1$ のときは長方形の $x<x_i$ をみたす領域
・$a_i=2$ のときは長方形の $x>x_i$ をみたす領域
・$a_i=3$ のときは長方形の $y<y_i$ をみたす領域
・$a_i=4$ のときは長方形の $y>y_i$ をみたす領域
を黒く塗りました。
塗りつぶしが終わったあとの長方形内での白い部分の面積を求めてください。

制約

・$1 \le W, H \le 100$
・$1 \le N \le 100$
・$0 \le x_i \le W~(1 \le i \le N)$
・$0 \le y_i \le H~(1 \le i \le N)$
・$W,H$ (21:32 追記), $x_i,y_i$ は整数である
・$a_i~(1 \le i \le N)$ は $1,2,3,4$ のいずれかである

収録されている問題セット

• AtCoder に登録したら次にやること (第07問類題)

回答

回答1 (AC)

白い部分は常に長方形になるので、その 4 辺を xl (左の辺), yu (上の辺), xr (右の辺), yl (下の辺) という変数で位置を保持します。初期状態は xl=0, yu=h, xr=w, yl=0 です。

$a_i=1$ のとき、$x<x_i$ の部分は白く塗られるので、xl$<x_i$ ならば xl を $x_i$ で更新します。$a_i=2,3,4$ の場合も同様です。

最後に白い部分の面積を計算します。xl<xr かつ yl<yu のときは白い長方形が残っているので、その面積 (xr-xl)*(yu-yl) を出力して終了します。そうでない場合には白い部分はなくなっている(黒で塗りつぶされた)ので、面積 0 を出力します。

ここまでの処理をまとめると以下のコードになりました。

abc047b-1.cpp

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

int main() {
  int w, h, n;
  cin >> w >> h >> n;

  int x, y, a;
  int xl = 0, xr = w, yl = 0, yu = h;
  for ( int i=0; i<n; i++ ) {
    cin >> x >> y >> a;
    if ( a==1 ) {
      if ( xl<x ) {
        xl = x;
      }
    } else if ( a==2 ) {
      if ( x<xr ) {
        xr = x;
      }
    } else if ( a==3 ) {
      if (yl<y) {
        yl = y;
      }
    } else {
      if ( y<yu ) {
        yu = y;
      }
    }
  }
  if ( xr>xl && yu>yl ) {
    cout << (xr-xl)*(yu-yl) << endl;
  } else {
    cout << 0 << endl;
  }
}

調べたこと

AtCoder の解説 → 公式解説

回答1と同じ方針でした。

リンク

前後の記事

• 前の記事 → AtCoderログ：0068 - ABC 213 B