D. Vanya and Triangles - 题解

比赛与标签

比赛: Codeforces Round 308 (Div. 2) 标签: brute force, combinatorics, data structures, geometry, math, sortings 难度: *1900

喵喵，题目在说什么呀？

主人你好呀~ 这道题是说，Vanya 在一个平面上画了 n 个不同的点，然后他想知道，用这些点作为顶点，可以组成多少个面积不为零的三角形呢？

简单来说，面积不为零的三角形，就是三个顶点不共线的三角形啦！如果三个点在同一条直线上，它们就没法围成一个真正的三角形，面积就是零了。

所以，我们的任务就是数一数，有多少种选出三个点的方法，能让这三个点不在同一条直线上。

输入:

• 第一行是一个整数 n，代表点的数量。
• 接下来 n 行，每行是两个整数 x 和 y，代表一个点的坐标。

输出:

• 一个整数，表示面积不为零的三角形的数量。

解题思路喵~

直接去数不共线的三个点有点麻烦呢，喵~ 这种时候，我们可以试试逆向思维，也就是所谓的“补集思想”哦！

总的三角形数量（不管共不共线）减去共线的三个点的组合数量，剩下的不就是我们想要的非共线三角形数量了嘛？

第一步：计算所有可能的三点组合

从 n 个点中任意选出 3 个点，一共有多少种选法呢？这是一个经典的组合问题，答案是 C(n, 3) 种，也就是 n * (n - 1) * (n - 2) / 6。这就是我们可能构成的“三角形”总数啦。

第二步：计算共线的三个点的组合数量

这是这道题最核心的部分！我们怎么才能高效地找出所有共线的三个点呢？

一个一个地枚举三个点 (i, j, k) 再判断它们是否共线，复杂度是 O(n³)，对于 n=2000 来说太慢了，肯定会超时的说！

我们可以换个更聪明的办法：固定一个点，看其他点和它的关系。

1. 我们遍历每一个点，把它当作“枢纽点”（pivot），我们叫它点 P 好了。
2. 对于这个枢纽点 P，我们再遍历所有其他的点，计算它们和点 P 连线所形成的斜率。
3. 如果好几个点（比如点 A, B, C）和点 P 的连线斜率都相同，那说明什么呢？说明 P, A, B, C 这些点都在同一条直线上！
4. 假设除了枢纽点 P 之外，还有 k 个点和 P 的斜率相同。那么在这 k 个点中，任意选出 2 个点，再配上枢纽点 P，就能组成一个三点共线的组合。从 k 个点中选 2 个，方法数是 C(k, 2) = k * (k - 1) / 2。

所以，我们的算法流程就是：

• 初始化共线三元组数量 collinear_triplets 为 0。
• 遍历所有点 i (从 0 到 n-1)，作为枢纽点。
• 对于每个枢纽点 i，我们用一个 map 来统计其他点 j (j > i) 与点 i 连线的斜率以及该斜率出现的次数。map<斜率, 次数>。
• 遍历完所有 j 之后，我们检查这个 map。如果某个斜率出现了 count 次（count >= 2），就说明有 count 个点和我们的枢纽点 i 形成了共线关系。这会产生 C(count, 2) 个新的共线三元组。我们把这个数量累加到 collinear_triplets 中。
• 循环结束后，collinear_triplets 就是所有共线三元组的总数啦。

一个重要的细节：如何表示斜率？

用浮点数 double 来表示斜率 dy/dx 是很危险的，因为会有精度问题喵！(>_<) 最好的办法是用一个最简分数来表示，也就是一对整数 (dy, dx)。

• 化简：计算出 dy 和 dx 后，我们求它们的最大公约数 g = gcd(abs(dy), abs(dx))，然后都除以 g。
• 统一表示：为了让 (2, 3) 和 (-2, -3) 被当成同一种斜率，我们要统一符号。一个简单的规则是，让 dx 始终为非负数。如果 dx 是负的，就把 dy 和 dx 都取反。
• 特殊情况：
  • 垂直线 (dx = 0)：斜率是无穷大。我们可以用一个特殊的数对来表示，比如 (1, 0)。
  • 水平线 (dy = 0)：斜率是 0。我们可以用 (0, 1) 来表示。

这样，每一种斜率都有一个独一无二的整数对表示，就可以放心地作为 map 的键啦！

最终答案：C(n, 3) - collinear_triplets。

代码实现の说

#include <iostream>
#include <vector>
#include <numeric> // 为了使用 std::gcd
#include <map>
#include <utility>

// 用一个结构体来存点的坐标，很清晰喵~
struct Point {
    int x, y;
};

// 这个函数用来获取斜率的“标准”表示形式，避免浮点数精度问题
// 斜率被表示成一个最简分数 (dy/dx)
std::pair<int, int> get_canonical_slope(int dy, int dx) {
    // 题目保证了点不重复，所以 dy 和 dx 不会同时为 0
    
    // 处理垂直线 (dx = 0)
    if (dx == 0) {
        return {1, 0}; // 所有垂直线都用这个来表示
    }
    // 处理水平线 (dy = 0)
    if (dy == 0) {
        return {0, 1}; // 所有水平线都用这个来表示
    }
    
    // 用最大公约数来化简分数
    int common_divisor = std::gcd(dy, dx);
    dy /= common_divisor;
    dx /= common_divisor;
    
    // 统一符号，我们规定 dx 必须是正数，这样表示才唯一
    if (dx < 0) {
        dx = -dx;
        dy = -dy;
    }
    
    return {dy, dx};
}

int main() {
    // 加速一下输入输出，跑得更快~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    int n;
    std::cin >> n;
    
    // 如果点数少于3个，肯定组不成三角形啦
    if (n < 3) {
        std::cout << 0 << std::endl;
        return 0;
    }
    
    std::vector<Point> points(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> points[i].x >> points[i].y;
    }
    
    // 先计算出从 n 个点里选 3 个的所有组合数，也就是 nC3
    long long total_triplets = (long long)n * (n - 1) * (n - 2) / 6;
    
    // 这个变量用来记录三点共线的组合数
    long long collinear_triplets = 0;
    
    // 遍历每个点，把它当作枢纽点
    for (int i = 0; i < n; ++i) {
        // map 用来存储从当前枢纽点 i 出发，到其他点的所有斜率的计数
        // key 是标准化的斜率(pair<int, int>), value 是这个斜率出现的次数
        std::map<std::pair<int, int>, int> slope_counts;
        
        // 遍历枢纽点 i 之后的所有点 j，避免重复计算
        for (int j = i + 1; j < n; ++j) {
            int dy = points[j].y - points[i].y;
            int dx = points[j].x - points[i].x;
            
            // 获取标准化的斜率，并给对应的计数器+1
            slope_counts[get_canonical_slope(dy, dx)]++;
        }
        
        // 统计完所有斜率后，开始计算由这个枢纽点 i 产生的共线三元组
        // 如果某个斜率出现了 count 次，说明有 count 个点和 i 共线
        // 这 count 个点可以组成 C(count, 2) 个点对，每个点对和 i 都能组成一个共线三元组
        for (auto const& [slope, count] : slope_counts) {
            if (count >= 2) {
                collinear_triplets += (long long)count * (count - 1) / 2;
            }
        }
    }
    
    // 最终答案 = 总组合数 - 共线组合数
    std::cout << total_triplets - collinear_triplets << std::endl;
    
    return 0;
}

复杂度分析喵

• 时间复杂度: O(N² log N) 的说。 我们有一个外层循环 for (int i = 0; i < n; ++i)，它会执行 N 次。内层循环 for (int j = i + 1; j < n; ++j) 最多也执行 N 次。在内层循环中，我们计算斜率并更新 std::map，map 的插入和访问操作的平均时间复杂度是 O(log K)，其中 K 是 map 中元素的数量，K 最多为 N。所以，这部分的主体是 O(N * N * log N)。后面的遍历 map 的操作复杂度较低。因此，总的时间复杂度是 O(N² log N)。对于 N=2000，这是完全可以接受的！

• 空间复杂度: O(N) 的说。 我们用 std::vector<Point> points 存储了所有 N 个点，这需要 O(N) 的空间。在每次外层循环中，我们创建了一个 slope_counts 的 map，它在最坏情况下（所有点都和枢纽点有不同斜率）会存储 N-1 个元素，所以也需要 O(N) 的空间。因为这个 map 是在循环内部的局部变量，每次循环都会重新创建，所以空间不会叠加。因此，总的空间复杂度是 O(N)。

知识点与总结

这道题真是一道融合了多种思想的经典好题呢，喵~

1. 补集思想 (Complementary Counting): 当直接计算目标（非共线）很困难时，不妨试试计算它的对立面（共线），再用总量减去它。这是组合数学中一个非常强大的武器哦！

2. 计算几何基础: 核心在于如何处理共线问题。通过固定一个点+计算斜率的方法，可以把三点共线问题转化为两点斜率问题，大大降低了思考的复杂度。

3. 避免浮点数精度问题: 在计算几何中，要对 double 或者 float 保持警惕！使用分数的规范化表示（比如化为最简整数对）是保证计算准确无误的标准操作。

4. 数据结构的选择: std::map 在这里简直是完美工具！它能自动地根据我们定义的键（这里是 std::pair）进行排序和分组，让我们能方便地统计相同斜率的数量。如果对性能有极致追求，也可以手写哈希函数用 std::unordered_map 来实现 O(N²) 的平均时间复杂度。

希望这篇题解能帮到主人哦！继续加油，算法的世界还有很多有趣的东西等着我们去探索呢，喵~ (ฅ'ω'ฅ)