AT_xmascon22_a Arte Del Latte

通过最多 $500$ 次“马布林（marbling）”操作，制作出如下图所示的接近目标的图像。**只要满足后述达成条件，输出的图片可以是彩色的。** 

输入按以下格式从标准输入给出。 > $W$ $H$ $N$ $G_0$ > $\vdots$ > $G_{H-1}$ $W, H$ 表示画布的宽度和高度，$N$ 表示马布林操作次数的上限。实际输入中 $H=W=N=500$。 $G_y$（$0 \leq y < H$）为长度为 $W$ 的字符串，表示目标图片中第 $y$ 行各像素的颜色。若目标图片像素 $(x, y)$ 处 $G_y$ 的第 $x$ 个字符为 `#`，则该像素为白色；为 `.` 时，则该像素为黑色。

> $M$ > $p_1$ > $\vdots$ > $p_M$ 第 $1$ 行输出一个整数 $M$（$0 \leq M \leq N$），表示马布林操作的次数。 接下来的 $M$ 行中，第 $i$（$1 \leq i \leq M$）行输出第 $i$ 次马布林操作，格式如下。 - 若执行 `drop` 操作，则 $p_i$ 为 `drop x y d r g b` 的格式 - 表示在点 $(x, y)$ 处滴下颜色为 $(r, g, b)$ 的颜料形成半径为 $d$ 的圆。 - 输出需满足以下条件： - $0 \leq x < W$，$0 \leq y < H$ - $0 \leq r \leq 255$，$0 \leq g \leq 255$，$0 \leq b \leq 255$ - $1 \leq d \leq 500$ - 若执行 `tine_line` 操作，则 $p_i$ 为 `tine_line x_1 y_1 x_2 y_2 z c` 的格式 - 表示沿经过两点 $A(x_1, y_1), B(x_2, y_2)$ 的直线，从 $A$ 指向 $B$ 的方向，在水面上用细棒划线；参数 $z, c$ 分别指定颜料的移动量和移动范围。 - 输出需满足以下条件： - $0 \leq x_1 < W$，$0 \leq y_1 < H$，$0 \leq x_2 < W$，$0 \leq y_2 < H$ - $A \ne B$（$x_1 \ne x_2$ 或 $y_1 \ne y_2$） - $1 \leq z \leq 100$ - $1 \leq c \leq 10$ 所有输出的数值必须为整数。

## 画布与马布林操作 用于绘制图像的画布大小为 $500$ 像素 $\times$ $500$ 像素，像素位置用整数对 $(x, y)$ 表示（$0 \leq x < 500$，$0 \leq y < 500$）。**注意，$x$ 坐标从左到右增大，$y$ 坐标从上到下增大。**每个像素有 $3$ 个元素表示其颜色：$R,G,B$。画布初始时，所有像素的 $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$ 到 $P$ 的距离小于等于 $d$，则该像素颜色变为 $(r, g, b)$。 - `tine_line`：沿经过两点 $A(x_1, y_1), B(x_2, y_2)$ 的直线，从 $A$ 朝 $B$ 的方向，用细棒划线；划线时颜料的移动量和作用范围由参数 $z, c$ 指定。 - 此操作将点 $P$ 的颜色按 $P + zu^d M$ 移动，其中 $z, u, d, M$ 含义如下： - 设 $N$ 为与 $\overrightarrow{AB}$ 垂直的单位向量，$d=|(P-B)\cdot N|$。 - $M$ 为与 $\overrightarrow{AB}$ 同向的单位向量。 - $1 \leq z \leq 100$，表示颜料移动量，是可设参数，$z$ 越大，沿直线的色彩变化越显著。 - $u = 2^{-1/c}$（$1 \leq c \leq 10$），表示颜料影响范围，可设参数，$c$ 越大，作用范围越大。 实际上，若点 $P$ 经操作移动为 $F(P)$，操作后像素 $Q$ 的颜色将设置为操作前最接近 $F^{-1}(Q)$ 的像素的颜色。画布外颜色一律视为黑色，即 $(R,G,B) = (0, 0, 0)$。 两种马布林操作的点的移动还满足以下关系，可在构造操作时利用： - 若 $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 \geq 255$，称为**明亮色**，否则称为**暗色**。若目标图像中白色区域为明亮色、黑色区域为暗色，则认为生成的图片达成目标。 具体来说，若目标图像与输出图像在**明暗不一致**的像素数不超过 $16\,000$，则视为 AC。 这里，像素 $(x, y)$ 的明暗不一致，指的是：目标图像在$(x, y)$为白色且输出图像为暗色，或目标图像为黑色且输出图像为明亮色。 ## 数据与可视化工具 **所需输入数据可以在[这里](https://img.atcoder.jp/xmascon22/1af1ad16495d0a52e7fc5c3598a79723.zip)下载。**zip 中包括如下文件： - `marbling/input.png`：目标图像。图片尺寸 $500 \times 500$ 像素。 - `marbling/input.txt`：对应于目标图像的输入数据，实际评测使用时与此一致。 另外，[**可视化工具**](http://japl.pl/xmas2022/marbling/40e14d5a3d.html)可进行操作序列可视化与达成条件判定。页面底部的“マーブリング操作を描画する”功能可读取正确格式的操作行（即按本题输出格式，首行会被跳过）。 由 ChatGPT 5 翻译