AT_xmascon22_a Arte Del Latte

マーブリングの操作を高々 $ 500 $ 回行うことで，以下の画像に近い画像を作り上げよ．**後述の達成条件を満たしていれば，カラフルな画像にしてもよい．** 

入力は以下の形式で標準入力から与えられる． > $ W $ $ H $ $ N $ $ G_0 $ $ \vdots $ $ G_{H-1} $ $ W, H $ はキャンバスの横および縦のサイズを， $ N $ はマーブリング操作の回数の上限を表す．実際の入力では $ H = W = N = 500 $ である． $ G_y $ ( $ 0 \le y < H $ ) は $ W $ 文字の文字列であり，目的画像の色を表す．目的画像の画素 $ (x, y) $ の色は， $ G_y $ の $ x $ 文字目が `#` のときは白であり，`.` のときは黒である．

> $ M $ $ p_1 $ $ \vdots $ $ p_M $ $ 1 $ 行目に，マーブリング操作の回数を表す整数 $ M $ ( $ 0 \le M \le N $ ) を出力せよ． 続く $ M $ 行のうち $ i $ ( $ 1 \le i \le M $ ) 行目には， $ i $ 回目のマーブリング操作を以下の形式で出力せよ． - `drop` の操作を行う場合 $ p_i $ は `drop x y d r g b` の形式 - これは点 $ (x, y) $ に色 $ (r, g, b) $ の絵の具を垂らして半径 $ d $ の円を作ることを表す． - 出力は以下の制約を満たす必要がある． - $ 0 \le x < W $ ， $ 0 \le y < H $ ． - $ 0 \le r \le 255 $ ， $ 0 \le g \le 255 $ ， $ 0 \le b \le 255 $ ． - $ 1 \le d \le 500 $ ． - `tine_line` の操作を行う場合 $ p_i $ は `tine_line x1 y1 x2 y2 z c` の形式 - これは $ 2 $ 点 $ A(x_1, y_1), B(x_2, y_2) $ を通る直線に沿って， $ A $ から $ B $ の方向へ，水面に細い棒を通すこと，またその際の絵の具の移動量・移動範囲を表すパラメタを $ z $ , $ c $ に指定することを表す． - 出力は以下の制約を満たす必要がある． - $ 0 \le x_1 < W $ ， $ 0 \le y_1 < H $ ， $ 0 \le x_2 < W $ ， $ 0 \le y_2 < H $ ． - $ A \neq B $ ( $ x_1 \neq x_2 $ または $ y_1 \neq y_2 $ )． - $ 1 \le z \le 100 $ ． - $ 1 \le c \le 10 $ ． 出力される数値はすべて整数でなければならない．

### キャンバスとマーブリング操作 画像を作るためのキャンバスは横 $ 500 $ px，縦 $ 500 $ px であり，画素の位置は整数の組 $ (x, y) $ ( $ 0 \le x < 500 $ ， $ 0 \le y < 500 $ ) で表される． **$ x $ 座標が増える方向が左から右へ， $ y $ 座標が増える方向が上から下へであることに注意せよ．**各画素は色を表す $ R,G,B $ の $ 3 $ 要素を持つ．はじめ，キャンバスのどの要素も $ R,G,B $ の値はすべて $ 0 $ である． キャンバスに対して，以下の $ 2 $ 種類のマーブリング操作を行うことができる． - `drop`: 画素 $ C(x, y) $ に色 $ (r, g, b) $ の絵の具を垂らして半径 $ d $ の円を作る． - この操作によって点 $ P $ の色は $ C + \sqrt{1+\frac{d^2}{|P-C|^2}} (P-C) $ に移動する． - ただし， $ C $ からの距離が $ d $ 以下の画素は色が $ (r, g, b) $ になる． - `tine_line`: $ 2 $ 点 $ A(x_1, y_1), B(x_2, y_2) $ を通る直線に沿って， $ A $ から $ B $ の方向へ，水面に細い棒を通す． - この操作によって点 $ P $ の色は $ P + zu^d M $ に移動する．ここで， $ z,u,d,M $ はそれぞれ以下のように決まる． - $ N $ を $ \overrightarrow{AB} $ に直交する単位ベクトルとして $ d=|(P-B)\cdot N| $ ． - $ M $ は $ \overrightarrow{AB} $ と同じ方向の単位ベクトル． - $ 1 \le z \le 100 $ は絵の具の移動量を表す指定可能なパラメタ．大きい方が色が線に沿ってより大きく動く． - $ u = 2^{-1/c} $ ( $ 1 \le c \le 10 $ ) は絵の具の移動の範囲を表す指定可能なパラメタ．大きい方がより周囲の色も巻き込んで動く． 実際には，点 $ P $ が操作によって $ F(P) $ に移るとき，操作後の画素 $ Q $ の色は操作前の画素 $ F^{-1}(Q) $ の色として決める (座標は最も近い整数に丸める)．また，キャンバスの範囲外の色はすべて黒 ( $ (R, G, B) = (0, 0, 0) $ ) とする． $ 2 $ 種類のマーブリング操作による点の移動について，以下が成り立つことを使ってもよい． - $ Q = C + \sqrt{1+\frac{d^2}{|P-C|^2}} (P-C) $ のとき， $ P = C + \sqrt{1-\frac{d^2}{|Q-C|^2}}(Q-C) $ - $ Q = P+zu^d M $ のとき， $ P = Q - zu^{d'}M $ (ここで $ d'=|(Q-B)\cdot N| $ ) ### 達成条件 色 $ (R, G, B) $ は $ R + G + B \ge 255 $ を満たすとき**明るい色**と言い， $ R + G + B < 255 $ のとき**暗い色**と言う．ある画像が「目的画像に近い」とみなされるためには，目的画像において白い部分が明るい色になっており，黒の部分が暗い色になっている必要がある． 厳密には，目的画像と出力画像で**明暗が不一致**であるような画素の数が $ 16\,000 $ 以下であれば AC となる． ここで，画素 $ (x, y) $ の明暗が不一致であるとは，画素 $ (x, y) $ の色が目的画像において白かつ出力画像において暗い色，もしくは目的画像において黒かつ出力画像において明るい色であることを言う． ### データ・ビジュアライザ **この問題を解くために必要なデータをまとめた zip ファイルが[こちら](https://img.atcoder.jp/xmascon22/1af1ad16495d0a52e7fc5c3598a79723.zip)からダウンロードできる．**zip 内には以下のファイルが入っている． - `marbling/input.png`: 目的画像．画像サイズは横 $ 500 $ px，縦 $ 500 $ px である． - `marbling/input.txt`: 目的画像に対応する入力データ．実際の採点に用いられるものと同一． また，[**ビジュアライザ**](http://japl.pl/xmas2022/marbling/40e14d5a3d.html)が利用可能である．操作列の可視化や，達成条件の判定などの機能を備えている．ページ下部の「マーブリング操作を描画する」機能は，正しいマーブリング操作を表す行だけを読み込む (よって，後述の出力形式に従ったものを入れたときは，最初の行は単に読み飛ばされる)．