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)$为白色且输出图像为暗色，或目标图像为黑色且输出图像为明亮色。

数据与可视化工具

**所需输入数据可以在这里下载。**zip 中包括如下文件：

• marbling/input.png：目标图像。图片尺寸 $500 \times 500$ 像素。
• marbling/input.txt：对应于目标图像的输入数据，实际评测使用时与此一致。

另外，可视化工具可进行操作序列可视化与达成条件判定。页面底部的“マーブリング操作を描画する”功能可读取正确格式的操作行（即按本题输出格式，首行会被跳过）。

由 ChatGPT 5 翻译