#P1686. [Usaco2005 Open]Waves 波纹

    ID: 707 传统题 1000ms 256MiB 尝试: 99 已通过: 46 难度: 5 上传者: 标签>CF1800普及+/提高-反射展开法固定一个变量消去另一维坐标变换Silver

[Usaco2005 Open]Waves 波纹

[USACO 2005 Open] Waves 波纹

题目描述

水面由整数坐标格表示,非河堤格的初始深度为 00。石子在位置 (X,Y)(X,Y)、时刻 TT 落水时,会产生一个深度贡献为 +1+1 的上凸波。这个波在第 TT 秒位于落水格,随后每秒沿菱形外圈扩展一格。在第 T+2T+2 秒,同一位置又产生一个以同样方式传播、深度贡献为 −1-1 的下凹波。没有河堤阻挡时,波在产生后第 dd 秒覆盖与起点的曼哈顿距离恰好为 dd 的格子。

有两条贯穿整个水面的竖直河堤,位于 x=B1x=B_1 和 x=B2x=B_2 两列,波不能穿过河堤。沿水平方向传播的波碰到河堤时会反射,反射轴位于河堤列和其相邻水面列之间。也就是说,如果一次水平传播本应进入河堤,它会消耗这一秒,留在同一水面列并改变之后的水平方向。河堤不改变波在竖直方向上的传播。

波相遇时互不改变方向。把同一时刻到达同一格子的所有波的贡献相加,得到这一格的深度。

  • 河堤所在格输出 X。
  • 深度为正、为零、为负的水面格,分别输出 *、-、o。

反射示意图 · 波的产生和传播示意图 · 叠加示意图

输入格式

第一行四个整数 P,B1,B2,RP,B_1,B_2,R,表示石子数、两条河堤的横坐标和要观察的时刻。1≤P≤51\le P\le5,−500000≤B1,B2≤500000-500000\le B_1,B_2\le500000,1≤R≤5000001\le R\le500000。

接下来 PP 行,每行三个整数 X,Y,TX,Y,T,表示一颗石子的落水坐标和落水时刻,三个整数均在 [−500000,500000][-500000,500000] 内。

保证两条河堤的横坐标不同,石子不会落在河堤上,也不会有两颗石子在同一时刻落到同一格。

输出格式

输出第 RR 秒水面的 9×99\times9 字符矩阵。第 1 行对应 y=4y=4,最后一行对应 y=−4y=-4。每行从左到右依次对应 x=−4,−3,…,4x=-4,-3,\ldots,4。

样例

2 4 100 4
-3 0 1
0 0 2
--------X
-*------X
*-*-*---X
-o-*-*--X
o-----*-X
-o-*-*--X
*-*-*---X
-*------X
--------X