SP22320 POLYDRAW - Polynomial Drawing

题目描述

如果你喜欢多项式，可能已经解决过一些问题，比如 [POLEVAL](../../problems/POLEVAL/)、[POLYNOM](../../problems/POLYNOM/) 或 [POLYTABL](../../problems/POLYTABL/) 等。然而，如果你对多项式的图像特别感兴趣，这里有一个适合你的挑战：给定一个多项式，你需要为其绘制图像文件。

输入格式

输入首先给出一个小于100的正整数 $t$，表示测试用例的数量。接着是 $t$ 个测试用例。每个测试用例提供一个“漂亮打印”格式的多项式，以最高四次为限。系数可能是整数或分数，所有数字（包括分子和分母）绝对值均不超过100。 - 若系数全为整数且多项式最高次数不超过1，多项式以单行给出（即为 _基准行_）。 - 若系数全为整数但多项式次数大于1，多项式用两行表示，第一行是指数，第二行即为 _基准行_。 - 若至少一个系数为分数，多项式用三行表示，第一行是指数以及分子，最后一行为分母。多项式按以下 **规范形式** 表示： - $x$ 的幂按降序排列，每种幂只出现一次。 - 连续的项之间有一个运算符（+ 或 -）。 - 系数绝对值为1时省略。 - 系数为0的项除非整个多项式为零，否则省略。 - 基准行中无多余空格，只有指数下方可能出现空格。分数用数字下方的横线表示，长度与分子或分母数字位数相同，若位数不同则为较长者，并对较短者右对齐。 ```

                          3 4  2                3  10        2
有效多项式示例：   --x +x     -x+2      5x +---       x -5
                          5                       100
```

```
                         -3 4  2        2           1                    3
无效多项式示例：  -x +x        x+3x      x---      4x -13      2x +-5
                          5                         7
```

在多项式的基准行后，加一个空格，然后是绘图范围信息。表示为 "\[a;b\]"，其中 a 和 b 为整数，范围限制在-10到10之间。

_注意：没有行尾空格，每个测试用例后都有一个空行。_

输出格式

对于每个测试用例，你需要生成一个压缩格式的 [PGM 图像文件](http://en.wikipedia.org/wiki/Netpbm_format#PGM_example)（类型P2），显示多项式的图像。输出的第一行是PGM头信息：“P2 \[w\] \[h\] 2”，其中 \[w\] 和 \[h\] 分别为图像的宽和高（参见示例下方）。接下来的1到3行包含输入中给出的多项式和绘制区间。由于这样会使PGM文件无效，每行必须以 "#" 和一个空格开头。然后是 h 行数据。每行由 w 个像素值组成，值之间用单个空格分隔。每个像素值为0（黑色）、1（灰色）或2（白色），表示图像中的一个像素。图像宽度根据区间 \[a;b\] 计算。所有图像的 x 方向和 y 方向均以 20px 为单位。对水平方向的每个像素，计算相应的 y 值，画一个黑色像素标记该点。如果计算的 y 值不完全匹配像素位置，选择与其距离最近的像素。如果有多个距离相同，选择较低值的像素。若计算正确，任何（中间）值绝对值不超过 $10^{18}$。图像高度取决于给定绘图区间内多项式的最小值和最大值，其中“最小值”和“最大值”指绘制点的y值，而不是 x 值对应的精确y值。y 值范围从小于最小值的最大整数到大于最大值的最小整数。所以如果 $y_{min} = -3.2$ 且 $y_{max} = 4$，则 y 范围从 -4 到 5，结果 h = 181。h 的值始终小于 1000。图像背景为白色。坐标系的所有格点用单个灰色像素标记。如果给定的x区间或计算的y范围包含零，则绘制x轴和/或y轴为1px宽灰线。在绘制包括网格的坐标系后，绘制多项式图像。对x方向每个像素，计算相应的y值，并作为单个黑色像素绘制。由于这种有效的PGM图像表示会产生相当大的图像文件，需要以 **egg格式**打印，该格式使用双遍游程编码压缩。头部添加了关于egg格式的信息：在PGM头部行之后，附一个空格和格式标识“(egg)”。egg文件的第二行是新附加的注释，包含压缩率信息：“# Compression: xx.xx%”。压缩率按"1-(egg-size/pgm-size)" 计算，其中 “size” 指纯图像大小，不包括头部、注释和换行符。压缩率表示为百分比，小数点后两位。在 _第一遍_ ，每行被编码。先去掉像素值之间的空格。然后，将超过三个像素长度的连续同色序列用括号替换，括号中包含颜色的连续像素总数。为识别颜色，不同类型的括号用于表示：圆括号用于白色，花括号用于灰色，方括号用于黑色。 **示例**：0 0 0 0 0 2 2 2 2 1 1 1 2 2 1 1 1 1 1 1 1 编码为 \[5\](4)11122{7} 在 _第二遍_ ，若有连续相同的行，则进行编码。编码后只保留首行，后面用尖括号 "< >" 标明连行总数。 ![](http://didax.heliohost.org/eggviewer/polydraw-example-3x.png) 不巧的是，egg格式未广泛传播，目前没有图像查看器能处理egg格式图像，除 [在线 egg查看器](http://didax.heliohost.org/eggviewer) 外。如需查看egg图片，建议使用该查看器：只需粘贴egg数据即可显示图像。右侧显示的是示例输出（放大3倍以便于识别像素）。 _注意：每个测试用例后打印一个空行，除最后一个测试用例。_ **本翻译由 AI 自动生成**