SP14978 UOFTBC - Homemade Asteroids

砰砰砰！ 大家都喜欢《小行星》这个经典的街机游戏，需要玩家操控宇宙飞船来消灭小行星。你爱上了这款游戏，于是自己在家开发了一个版本！不过，不太完美。 在你的版本里，游戏在一个二维平面上进行，飞船是一个位于 ( $ X_S $ , $ Y_S $ ) 坐标的小点，周围有 $ N $ 个静止不动的三角形小行星，每个小行星都有一个正面积。第 $ i $ 个小行星的三个顶点坐标是 ( $ X_{Ai} $ , $ Y_{Ai} $ )、( $ X_{Bi} $ , $ Y_{Bi} $ ) 和 ( $ X_{Ci} $ , $ Y_{Ci} $ )。这些坐标都是绝对值不超过 $ 10^9 $ 的整数，并且所有的物体，甚至是边缘和顶点，都不重叠。 在游戏中，你只能发射一枚导弹。导弹沿着直线轨迹飞行，途中接触到的小行星都会被摧毁，包括在边缘或顶点上的部分。不过，它的运动不是完全连续的。导弹从飞船位置出发，初始时刻为第 0 帧，每经过一帧，其 x 坐标增加 $ X_D $ ，y 坐标增加 $ Y_D $ 。这些变化的绝对值也不超过 $ 10^9 $ ，且至少有一个非零。在经过第 $ F $ 帧（ $ 1 \leq F \leq 1000 $ ）后，导弹将消失。 总共给出 $ T $ 个这样的情景（ $ 1 \leq T \leq 20 $ ）。对于每个情景，你需要预测在第 $ F+1 $ 帧之前，导弹能摧毁多少个不同的小行星。

第一行：1 个整数 $ T $ ，表示有多少个情景。 对于每个情景： - 第一行：2 个整数 $ N $ 和 $ F $，分别表示小行星的数量和导弹飞行的帧数。 - 第二行：4 个整数 $ X_S $ 、$ Y_S $ 、$ X_D $ 和 $ Y_D $，表示飞船的初始坐标和导弹每帧的位移。 - 接下来 $ N $ 行：每行有 6 个整数，依次为 $ X_{Ai} $ 、$ Y_{Ai} $ 、$ X_{Bi} $ 、$ Y_{Bi} $ 、$ X_{Ci} $ 、$ Y_{Ci} $，代表每个小行星的顶点坐标。

对于每个情景，输出 1 个整数，表示导弹能摧毁的小行星数量。

- $ 1 \leq T \leq 20 $ - $ 1 \leq N \leq 1000 $ - $ 1 \leq F \leq 1000 $ - 所有坐标和位移 $ X_S, Y_S, X_{Ai}, Y_{Ai}, X_{Bi}, Y_{Bi}, X_{Ci}, Y_{Ci}, X_D, Y_D $ 均为 $ -10^9 $ 至 $ 10^9 $ 之间的整数。 **本翻译由 AI 自动生成**