D. Satyam and Counting - 题解

比赛与标签

比赛: Codeforces Round 971 (Div. 4) 标签: geometry, math 难度: *1400

题目大意喵~ 🐾

你好呀，未来的算法大师！这道题是说，在一个二维平面上，给了我们 n 个不同的点 (xi, yi)。有一个非常重要的特点哦：所有点的 y 坐标要么是 0，要么是 1！也就是说，所有的点都分布在 y=0 和 y=1 这两条水平线上，喵~

我们的任务呢，就是要从这些点中选出三个不同的点，看看能组成多少个不重合的、非退化（也就是有面积）的直角三角形。

输入格式：

先是一个整数 t，表示有 t 组测试数据。
每组数据第一行是一个整数 n，表示点的数量。
接下来 n 行，每行是两个整数 xi 和 yi，代表一个点的坐标。

输出格式：

对每组测试数据，输出一个整数，表示能组成的直角三角形的数量。

解题思路ニャ！💡

看到这道题，第一反应可能是“哇，几何题，好可怕！”。但别怕别怕，猫娘我来带你分析，你会发现它其实是一只温顺的小猫咪~

最关键的信息就是所有点都在 y=0 和 y=1 这两条线上。这大大简化了问题！一个三角形要想不退化（不成一条直线），它的三个顶点就不能都在同一条线上。所以，任何一个我们找到的三角形，都必须是两个顶点在一条线上，另一个顶点在另一条线上。

好，我们来想想直角三角形的构成。一个三角形 ABC，如果要在顶点 B 形成直角，那么向量 BA 和向量 BC 必须垂直。用坐标表示就是它们的点积为零： (xA - xB) * (xC - xB) + (yA - yB) * (yC - yB) = 0

根据这个性质，我们可以把所有可能的直角三角形分成两大类来数，这样就不会漏掉也不会重复计算啦！

情况一：直角边与坐标轴平行的三角形

这种是最常见的直角三角形了！它的两条直角边分别平行于 x 轴和 y 轴。

假设直角顶点是 B(xB, yB)，那么另外两个顶点 A 和 C 的坐标就必须是 (xB, yA) 和 (xC, yB)。

为了让 AB 垂直于 BC，A 和 B 的 x 坐标相同，B 和 C 的 y 坐标相同。
因为所有点都在 y=0 或 y=1 上，所以 yA 必须是 1 - yB。

所以，这种三角形的三个顶点是 (xB, yB), (xB, 1-yB), (xC, yB)。这告诉我们，要形成这样的三角形，必须存在一个 x 坐标，它在 y=0 和 y=1 上都有点。我们把这种 x 坐标叫做"公共 x 坐标"。

如果直角顶点在 y=0 上，比如是 (x_common, 0)。那么另外两个顶点必须是 (x_common, 1) 和另一个在 y=0 上的点 (x_other, 0)。有多少种选择呢？对于每一个公共 x 坐标，我们都可以搭配 y=0 上除了 (x_common, 0) 之外的所有点。如果 y=0 上有 N0 个点，那么就有 N0 - 1 种选择。
如果直角顶点在 y=1 上，同理，就是 (x_common, 1)。可以搭配 y=1 上除了它自己以外的所有点，也就是 N1 - 1 种选择。

所以，总数就是：公共x坐标的数量 * ( (N0 - 1) + (N1 - 1) )。

情况二：直角边是倾斜的三角形

这种情况稍微需要动动脑筋，但也很简单！我们再回到点积公式： (xA - xB) * (xC - xB) + (yA - yB) * (yC - yB) = 0

假设直角顶点 B 在 y=0 上，即 B(xB, 0)。那么另外两个顶点 A 和 C 就必须都在 y=1 上，即 A(xA, 1) 和 C(xC, 1)。

代入公式： (xA - xB) * (xC - xB) + (1 - 0) * (1 - 0) = 0(xA - xB) * (xC - xB) + 1 = 0(xA - xB) * (xC - xB) = -1

因为点的坐标都是整数，所以 (xA - xB) 和 (xC - xB) 也都是整数。两个整数相乘等于 -1，只有两种可能：1 * -1 或者 -1 * 1。这意味着： xA - xB = 1 且 xC - xB = -1 （或者反过来）也就是 xA = xB + 1 且 xC = xB - 1。

哇！也就是说，如果直角顶点是 (x, 0)，那么另外两个顶点必须是 (x-1, 1) 和 (x+1, 1)！对称地，如果直角顶点是 (x, 1)，另两个顶点就必须是 (x-1, 0) 和 (x+1, 0)。

所以，我们只需要：

遍历所有在 y=0 上的点 (x, 0)，检查 (x-1, 1) 和 (x+1, 1) 是否都存在。
遍历所有在 y=1 上的点 (x, 1)，检查 (x-1, 0) 和 (x+1, 0) 是否都存在。

为了快速检查某个点是否存在，我们可以先把 y=0 和 y=1 两条线上的所有点的 x 坐标分别存到哈希集合（unordered_set）里，这样查询就超级快啦，平均只要 O(1) 的时间！

把这两种情况加起来，就是最终的答案啦，喵~

代码实现，喵！💻

cpp

#include <iostream>
#include <vector>
#include <unordered_set>

void solve() {
    int n;
    std::cin >> n;
    // 分别存储 y=0 和 y=1 两条线上的点的 x 坐标
    std::vector<int> line0_x, line1_x;
    for (int i = 0; i < n; ++i) {
        int x, y;
        std::cin >> x >> y;
        if (y == 0) {
            line0_x.push_back(x);
        } else {
            line1_x.push_back(x);
        }
    }

    long long ans = 0;
    long long N0 = line0_x.size();
    long long N1 = line1_x.size();

    // 如果所有点都在一条线上，是无法构成三角形的，喵~
    if (N0 == 0 || N1 == 0) {
        std::cout << 0 << "\n";
        return;
    }

    // 使用哈希集合来快速查找某个 x 坐标是否存在
    std::unordered_set<int> set0(line0_x.begin(), line0_x.end());
    std::unordered_set<int> set1(line1_x.begin(), line1_x.end());

    // --- 情况一：计算直角边与坐标轴平行的三角形 ---
    long long common_x_count = 0;
    // 为了效率，我们遍历较短的那个点集，去另一个哈希集合里查找
    if (N0 < N1) {
        for (int x : line0_x) {
            if (set1.count(x)) { // .count() 在哈希集合中是 O(1) 平均时间
                common_x_count++;
            }
        }
    } else {
        for (int x : line1_x) {
            if (set0.count(x)) {
                common_x_count++;
            }
        }
    }
    
    // 对于每个公共x坐标，都可以形成两种直角三角形
    // 1. 直角顶点在 y=0 上: common_x_count * (N0 - 1) 个
    // 2. 直角顶点在 y=1 上: common_x_count * (N1 - 1) 个
    if (N0 > 1) {
        ans += common_x_count * (N0 - 1);
    }
    if (N1 > 1) {
        ans += common_x_count * (N1 - 1);
    }

    // --- 情况二：计算直角边是倾斜的三角形 ---
    // Case 1: 直角顶点在 y=0 上
    for (int x : line0_x) {
        // 检查 (x-1, 1) 和 (x+1, 1) 是否存在
        if (set1.count(x - 1) && set1.count(x + 1)) {
            ans++;
        }
    }
    // Case 2: 直角顶点在 y=1 上
    for (int x : line1_x) {
        // 检查 (x-1, 0) 和 (x+1, 0) 是否存在
        if (set0.count(x - 1) && set0.count(x + 1)) {
            ans++;
        }
    }

    std::cout << ans << "\n";
}

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

复杂度分析的说 ⏱️

时间复杂度: O(N) 的说。
- 读取输入并将点的 x 坐标分类存放需要 O(N) 时间。
- 将 x 坐标放入两个哈希集合，平均情况下需要 O(N) 时间。
- 计算公共 x 坐标的数量，我们遍历了较小的点集，所以是 O(min(N0, N1))，也就是 O(N)。
- 计算倾斜三角形时，我们遍历了 line0_x 和 line1_x 各一次，内部的哈希查询是 O(1) 的，所以这部分是 O(N0 + N1) = O(N)。
- 总的时间复杂度就是 O(N) + O(N) + O(N) = O(N) 啦！非常高效！
空间复杂度: O(N) 的说。
- 我们用了两个 vector (line0_x, line1_x) 和两个 unordered_set (set0, set1) 来存储所有点的 x 坐标。它们加起来总共需要 O(N) 的空间。

知识点与总结，喵呜~ 🎓

这道题真可爱，对吧！它告诉我们，看似复杂的几何问题，只要抓住关键的限制条件（比如 y 坐标只有0和1），就可以通过巧妙的 分类讨论 来解决！

抓住问题核心: y 坐标的限制是解题的突破口，它将问题从一个通用的2D几何问题简化为一个在两条平行线上的特殊问题。
分类讨论思想: 将直角三角形分为“轴对齐”和“倾斜”两类，确保了计数的完备性和无重复性，这是组合计数问题中非常重要的思想。
善用数据结构: 使用 std::unordered_set（哈希集合）进行快速查找，是让算法达到线性时间复杂度的关键。不然每次查找都遍历数组，时间复杂度会飙升到 O(N^2)，肯定会超时的说。
几何性质的应用: 向量点积为零是判断垂直的根本方法。从这个基本性质出发，我们推导出了倾斜三角形的顶点坐标关系，非常酷！

希望这篇题解能帮到你！继续加油，享受每一道题带来的挑战和乐趣吧，喵~ ✨

D. Satyam and Counting - 题解 ​

比赛与标签 ​

题目大意喵~ 🐾 ​

解题思路ニャ！💡 ​

情况一：直角边与坐标轴平行的三角形 ​

情况二：直角边是倾斜的三角形 ​

代码实现，喵！💻 ​

复杂度分析的说 ⏱️ ​

知识点与总结，喵呜~ 🎓 ​