きままにものづくり

日々の気付いたことなんかを書いてます。

AOJ 0531 : Paint Color

問題

幅W(1 \leq W \leq 10^6)高さH(1 \leq H \leq 10^6)の平面を考える。この平面内にN(N \leq 10^3)の矩形が存在する。与えられた平面は、矩形により、いくつに分割されるか求めよ。

解法

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

計算量

 O(6*N*6*N)
N : 矩形の数

コード

広告を非表示にする