← 返回题目列表

AtCoder · xmascon22_a

A. 拿铁艺术

中文机器翻译题面 查看原题

配点 : 100 点

兔子想要学会制作拉花,但它发现每次练习都要喝咖啡拉花是很困难的。

因此兔子决定,作为替代玩大理石纹(Marbling)。

問題文

通过最多 500 次大理石纹操作,制作出接近以下图片的图像。如果满足后述的达成条件,也可以制作彩色图像。

bb57367da6d3e7086ea305781b31e51c.png

画布和大理石纹操作

用于制作图像的画布宽度为 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 内包含如下文件。

  • marbling/input.png: 目标图像。图像尺寸为横向 500 px,纵向 500 px。
  • marbling/input.txt: 与目标图像对应的输入数据。与实际评分时使用的相同。

另外, 如果我们只为第展示台可用。具有操作序列可视化、判断达成条件等功能。页面底部的“绘制大理石操作”功能只读取表示正确大理石操作的行(因此,当输入符合后述输出格式时,第一行会被简单跳过)。


入力

输入是按以下格式从标准输入给出的。

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 请以以下形式输出第n次大理石纹操作。

  • 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.

输出的数值必须全部为整数。