← 返回题目列表

Codeforces · 2120/B

B. 方池

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

Aryan 和 Harshith 正在 AX120 宇宙中的 $$$s$$$ 边的固定方形台球桌上打台球, 口袋 在其 $$$4$$$ 角落。角点位于 $$$(0,0)$$$、$$$(0,s)$$$、$$$(s,0)$$$ 和 $$$(s,s)$$$。在这个游戏变体中,$$$n$$$ 相同的球被放置在具有完整坐标的桌子上,使得没有球位于桌子的边缘或角落。然后,它们全部以 $$$10^{100}$$$ 单位/秒的速度同时拍摄(仅以 $$$45$$$ 与轴的度数)。

在宇宙 AX120 中,球和口袋几乎都是点大小的,并且碰撞是弹性的,即球在击中任何表面时,都会以相同的角度和相同的速度反弹。

Harshith 投篮,他向 ​​Aryan 提供了球的位置和投篮角度。帮助雅利安确定放入罐中的球的数量 口袋 ,作者:Harshith。

保证在同一时刻、同一位置不会发生多次碰撞。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$s$$$ ($$$1 \le n \le 10^3$$$, $$$2 \le s\le 10^9$$$) — 桌上放置的球的数量和方形台球桌的边长。

接下来的 $$$n$$$ 行的第 $$$i$$$ 包含四个整数 $$$d_x$$$、$$$d_y$$$、$$$x_i$$$ 和 $$$y_i$$$ ($$$d_x,d_y \in \{-1, 1\}$$$, $$$0 \lt x_i, y_i \lt s$$$) — 分别在 $$$X$$$ 轴和 $$$Y$$$ 轴上的发射方向向量,以及第 $$$i$$$ 球放置位置的坐标。保证在初始时刻没有两个球重合。

还保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^3$$$。

输出

对于每个测试用例,打印一个整数 - 该游戏中入袋的球数。

示例

输入
复制

2
1 2
1 1 1 1
5 4
1 -1 1 1
1 -1 2 2
-1 1 2 3
1 -1 1 3
-1 1 3 1

输出
复制

1
3

注意

在第一个测试用例中,有一个球,它直接射向 $$$(2, 2)$$$ 的口袋,从而入袋。

在第二个测试用例中,状态进展为

$$$\右箭头$$$
$$$\右箭头$$$
$$$\右箭头$$$
$$$\右箭头$$$