アルゴリズム忘備録

競技プログラミングとかデータ分析とか

AtCoder Regular Contest 073 E: Ball Coloring

arc073.contest.atcoder.jp

 

(x[i], y[i]) (1≦i≦N) が与えられる。任意の点について、xとyを交換できるとき、これらの点をすべて含み、辺がx軸またはy軸に平行な長方形の面積の最小値を求めよ。

 

まずすべての点についてx[i]≦y[i]となるようにしておく。この時をminX, maxYとするとき、次の2パターンが存在する。

  1. max(y[i]) - min(x[i]) の長さの辺がある
  2. 角の座標が(min(x[i]), max(y[i]))となる

2の場合はもう一つの角の座標が(max(x[i]), min(y[i])) なので、これで面積が出る。

1の場合は残りの辺の最大の高さh=max(x[i])として、x[i]を小さい方から見ていき、h - x[i] をもう一方の辺の長さとして面積を計算する。hは今見ているx[i]に対応するy[i]とのmaxを取り更新、次の辺について調べる。x[i]がmin(y[i])を超えない範囲で調べた後、min(y[i])が角のy座標になるパターンも調べてそれぞれの最小値を求める。O(N)。