問題文

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

キャンバスとマーブリング操作

画像を作るためのキャンバスは横 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 ファイルがこちらからダウンロードできる．zip 内には以下のファイルが入っている．

• marbling/input.png: 目的画像．画像サイズは横 500 px，縦 500 px である．
• marbling/input.txt: 目的画像に対応する入力データ．実際の採点に用いられるものと同一．

また，ビジュアライザが利用可能である．操作列の可視化や，達成条件の判定などの機能を備えている．ページ下部の「マーブリング操作を描画する」機能は，正しいマーブリング操作を表す行だけを読み込む (よって，後述の出力形式に従ったものを入れたときは，最初の行は単に読み飛ばされる)．