1009 Edge Detection

原文

時間制限:1000ミリ秒
メモリ制限:10000KB

輪郭検出

問題

IONU衛星画像株式会社は、非常に大きな画像をランレングス圧縮を用いて記録し保存している。あなたはその画像を読みとり、検出された辺に基づく新たな圧縮画像を生成するプログラムを書かなければならない。
単純な輪郭検出アルゴリズムにおいて、出力ピクセルの値は入力の対応するピクセルとその周囲のピクセルとの差の絶対値の最大値である。例えば以下のイメージを考える:

出力の左上のピクセルは、|15-15|,|15-100|,|15-100|のうちの最大値つまり85である。4行2列目のピクセルは、|175-100|、|175-100|、|175-100|、|175-175|、|175-25|、|175-175|、|175-175|、|175-25|のうちの最大値、つまり150となる。
画像は2以上1,000,000,000(109)個のピクセルを含む。全ての画像はランレングス圧縮(RLE)を用いて符号化される。これはピクセル値(0-255)とランレングス(1-109)のペアの列であらわされる。入力画像は最大でもこれらのペアを1,000個しかもたない。隣接しているペアは異なるピクセル値をもつ。画像のどの行や列も同じ個数のピクセルを持つ。

入力

入力は1つ以上の画像についての情報からなる。各画像は横のピクセル数(幅)を含む行からはじまる。続く行にはそれぞれ1つづつRLEペアが書かれている。0 0という行がその画像に対するデータの終わりを意味する。幅0の画像は入力の終端を意味する。サンプルデータの最初の画像は上記入力イメージをエンコードしたものである。

出力

出力は、1,000以上のRLEペアが出現しうることを除いて、入力と同じフォーマットの画像データの列である。

入力例

7
15 4
100 15
25 2
175 2
25 5
175 2
25 5
0 0
10
35 500000000
200 500000000
0 0
3
255 1
10 1
255 2
10 1
255 2
10 1
255 1
0 0
0

出力例

7
85 5
0 2
85 5
75 10
150 2
75 3
0 2
150 2
0 4
0 0
10
0 499999990
165 20
0 499999990
0 0
3
245 9
0 0
0

ヒント

ブルートフォース(力ずく)の方法として、それぞれのピクセルを直に計算しようとすると、おそらく時間かメモリの問題で失敗する。

出典

Mid-Central USA 2000