AOJ 0531 : Paint Color
問題
幅W()高さH(
)の平面を考える。この平面内にN(
)の矩形が存在する。与えられた平面は、矩形により、いくつに分割されるか求めよ。
解法
座標圧縮を用いて計算量を減らす。与えられる数字は整数だが、分割されているかを判断する際には小数を考慮しなければならない。高さは1とした時、x=5までの矩形とx=6から始まる矩形が存在するとする。実際は、5と6の間には領域が存在するが整数のみで考えていると間は何もないとしてしまう。
与えられる数字は整数なので、ちょうど中間の0.5を考慮すればよい。小数の座標を考慮すると計算が複雑になるので、与えられる整数全てを2倍することにより整数のみの計算で間を考慮することができる。
今回のケースは、WとHも含む形式となっている。座標圧縮で返す値を-1とすることで、以降の計算でも同様の境界条件を適用できる。
計算量
N : 矩形の数
