题目

传送门 to CF

传送门 to VJ

题意概要
在一个平面直角坐标系内，纵轴和横轴上各有一些人。他们有各自的出发时间，行走方向垂直于初始所在的坐标轴，并且按照一个单位每秒的速度前进。

点击此处查看图片

如果两个人刚好相遇，这二人互换移动方向。毫无疑问，时间足够长，每个人都不会再相遇了。求每个人最后会往何方向走。

思路

像这种“交换方向”的操作，往往可以看成没有发生变化：两个人擦身而过，交换了身份证而已。

考虑两个人 $i,j$i,j ，不妨设 $i$i 从 $(x_i,0)$(xi​,0) 出发， $j$j 从 $(y_j,0)$(yj​,0) 出发。二者相遇的地点一定是 $(x_i,y_j)$(xi​,yj​) ，那么 $i$i 会在 $t_i+y_j$ti​+yj​ 时刻到达，而 $j$j 会在 $t_j+x_i$tj​+xi​ 时刻到达。所以，相遇的条件是 $x_i+t_j=y_j+t_i\;\Leftrightarrow\;x_i-t_i=y_j-t_j$xi​+tj​=yj​+ti​⇔xi​−ti​=yj​−tj​

所以，我们把 $x_i-t_i$xi​−ti​ 相同的，视为一组。显然，组内的人都是恰好相遇，不是一组以内的人不会相逢。所以，我们只考虑某一组的变化。

用从 $y$y 轴上出发的人举例； $x$x 轴上出发则是类似的。

本质就是在一个网格图中行走，遇到格点强制性转弯。它会转弯多少次呢？

记录其右边的竖线数量（也就是网格图的长）为 $b$b ，上方的横线数量（网格图的宽）为 $a$a 。此处的“上方”并不包含自己。譬如上图，应当是 $a=2,b=4$a=2,b=4 的情况。

• 当 $a<b$a<b 时（如上图所示），它最后会沿着某条竖线离开，恰好是第 $a+1$a+1 条。
• 当 $a\ge b$a≥b 时，自然就会沿着某条横线离开，恰好是第 $b$b 条。

所以就没了。

代码

然鹅我并没有打代码，因为我很忙。

编的一手好借口，听上去还有几分嚣张