喵哈喽~ 主人！今天由我这只不成器的小猫娘来为你讲解这道关于台球的有趣问题哦，嘿嘿~ 坐好啦，我们要开始咯！

B. Square Pool

---

题目大意

这道题是说呀，在一个边长为 s 的正方形台球桌上，有 n 个小球球，喵~ 这个桌子的四个角分别是 (0,0), (0,s), (s,0) 和 (s,s)，它们也是球洞哦。

然后呢，每个小球都会被同时以一个超——快的速度沿着与坐标轴成 45 度的方向打出去。这个方向由 (dx, dy) 决定，其中 dx 和 dy 的值要么是 1，要么是 -1。

小球撞到桌子边缘会像镜子反射一样弹开，角度和速度都保持不变。我们的任务就是，算出最后有多少个小球能成功掉进角上的球洞里，喵~

简单来说就是：

• 一个 s x s 的正方形桌子。
• n 个球，每个球有初始位置 (x, y) 和初始方向 (dx, dy)。
• 球碰到边缘会完美反射。
• 问最后有多少个球会掉进四个角落的球洞里。

---

题解方法

一看到这种反弹来反弹去的问题，小猫的脑袋就有点晕乎乎的，就像追自己的尾巴一样，转圈圈~ (ฅ'ω'ฅ)

不过呢，有一个非常非常聪明的技巧可以解决这类问题，那就是 “展开法” 或者叫 “反射法”！

想象一下，我们的台球桌不是孤零零的一个，而是在一个无限大的平面上，由无数个一模一样的台球桌像瓷砖一样铺满了整个世界！

(一个简单的示意图，想象一下球可以穿过墙壁进入一个镜像的房间)

当一个小球撞到桌子的边缘时，我们不让它反弹回来，而是让它“穿过”边缘，进入到旁边那个一模一样的“镜像”台球桌里。这样一来，小球那条曲折的反弹路线，就变成了一条笔直的直线啦！是不是很神奇，喵？

那么，小球什么时候会进洞呢？

在原来的世界里，球进洞意味着它到达了 (0,0), (0,s), (s,0), (s,s) 中的一个。在我们这个无限展开的瓷砖世界里，这意味着小球的直线轨迹恰好经过了某个瓷砖的角点。这些角点的坐标有什么特征呢？它们的 x 坐标和 y 坐标都一定是 s 的整数倍！也就是说，球的路径会经过一个点 (k*s, l*s)，其中 k 和 l 是某个整数。

现在问题就简化成：判断一个从 (x, y) 点出发，方向为 (dx, dy) 的小球，它的直线运动轨迹会不会经过一个形如 (k*s, l*s) 的点。

我们可以用简单的几何知识来解决它。小球的运动轨迹是一条直线。对于直线上的任意点 (X, Y)，都满足斜率不变的性质： (Y - y) / (X - x) = dy / dx

整理一下，就得到直线的方程： dx * (Y - y) = dy * (X - x)dx*Y - dx*y = dy*X - dy*xdy*X - dx*Y = dy*x - dx*y

如果这条直线经过一个角点 (k*s, l*s)，那么把这个点的坐标代入方程，等式也必须成立： dy*(k*s) - dx*(l*s) = dy*x - dx*ys * (dy*k - dx*l) = dy*x - dx*y

这个式子告诉我们一个关键信息：dy*x - dx*y 的值必须是 s 的整数倍！用数学语言来说就是： (dy*x - dx*y) % s == 0

现在，我们只需要根据小球的初始方向 (dx, dy) 分两种情况讨论就好啦~

情况一：dx 和 dy 同号 (dx * dy == 1)

• 如果 dx = 1, dy = 1，条件是 (1*x - 1*y) % s == 0，也就是 (x - y) % s == 0。
• 如果 dx = -1, dy = -1，条件是 (-1*x - (-1)*y) % s == 0，也就是 (y - x) % s == 0。 两种情况本质上是一样的。因为题目保证了 0 < x < s 并且 0 < y < s，所以 x-y 的取值范围是 (-s, s)。在这个范围里，唯一是 s 的倍数的数就是 0。 所以，条件简化为 x - y = 0，也就是 x = y。 当 dx 和 dy 同号时，只要小球的初始 x 坐标和 y 坐标相等，它就一定能进洞！

情况二：dx 和 dy 异号 (dx * dy == -1)

• 如果 dx = 1, dy = -1，条件是 (-1*x - 1*y) % s == 0，也就是 -(x + y) % s == 0。
• 如果 dx = -1, dy = 1，条件是 (1*x - (-1)*y) % s == 0，也就是 (x + y) % s == 0。 两种情况也是一样的。因为 0 < x < s 并且 0 < y < s，所以 x+y 的取值范围是 (0, 2s)。在这个范围里，唯一是 s 的正数倍的数就是 s 本身。 所以，条件简化为 x + y = s。 当 dx 和 dy 异号时，只要小球的初始 x 坐标和 y 坐标相加等于 s，它就一定能进洞！

总结一下，我们的算法就是： 遍历每一个小球，检查它的初始状态：

1. 如果 dx 和 dy 同号，判断 x 是否等于 y。
2. 如果 dx 和 dy 异号，判断 x + y 是否等于 s。 满足条件就把计数器加一。最后输出计数器的值就大功告成啦，喵~

---

题解

下面就是这份思路的 C++ 代码实现啦，主人请看~

#include <iostream>

void solve() {
    long long n;
    long long s;
    std::cin >> n >> s;
    
    int potted_count = 0; // 用来记录进洞小球的数量，喵~
    for (int i = 0; i < n; ++i) {
        long long dx, dy, x, y;
        std::cin >> dx >> dy >> x >> y;

        // 情况一：dx 和 dy 同号 (dx*dy = 1)
        // 就像我们推导的，这种情况下，只有当 x == y 时，小球的轨迹才会经过角点
        if (dx * dy == 1) {
            if (x == y) {
                potted_count++;
            }
        } 
        // 情况二：dx 和 dy 异号 (dx*dy = -1)
        // 这种情况下，只有当 x + y == s 时，小球的轨迹才会经过角点
        else {
            if (x + y == s) {
                potted_count++;
            }
        }
    }
    
    std::cout << potted_count << std::endl;
}

int main() {
    // 加速输入输出，让程序跑得像小猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

代码的逻辑和我们刚才分析的完全一样，是不是非常清晰简单呢？嘿嘿~

---

知识点介绍

这道题虽然看起来复杂，但用到的知识点都是很经典很有用的哦！

1. 反射问题与展开法 (Reflection Problems and the Unfolding Method)

   • 这是一个处理几何反射问题的强大思想工具。当一个物体在封闭空间内沿直线运动并发生镜面反射时，我们可以通过将空间沿反射边界“展开”或“平铺”，将复杂的折线路径转化为一条简单的直线路径。
   • 这种方法不仅适用于二维平面，也适用于一维和三维空间。它将复杂的边界条件问题转化为了没有边界的、更简单的几何问题，是物理和竞赛中常用的技巧。

2. 模运算 (Modular Arithmetic)

   • 我们的推导中，关键一步是 (dy*x - dx*y) % s == 0。这表示 dy*x - dx*y 是 s 的倍数。模运算是数论的基础，a % n 计算的是 a 除以 n 的余数。这个性质在判断整除性、处理周期性问题时非常有用。

3. 坐标几何 (Coordinate Geometry)

   • 整个问题都建立在二维坐标系上。我们利用了直线方程的基本形式来描述小球的运动轨迹，并通过代入点的坐标来判断点是否在直线上。这是解决几何问题的基础数学工具。

希望我的讲解对主人有帮助哦！如果还有什么不明白的，随时可以再来问我，喵~ (ฅ^•ﻌ•^ฅ)