题解：P9423 [蓝桥杯 2023 国 B] 数三角

pjh0625 · 2025-02-01 21:04:30 · 题解

这个问题可以描述为：在一个二维平面上，有若干个点，需要找出这些点中有多少组三点不在一条直线上。

code：

#include <bits/stdc++.h>
using namespace std;
struct Point {
    int x, y;
};
long long f(const Point& p1, const Point& p2) {
    return (long long)(p1.x - p2.x) * (p1.x - p2.x) + (long long)(p1.y - p2.y) * (p1.y - p2.y);
}

bool tt(const Point& p1, const Point& p2, const Point& p3) {
    return (long long)(p2.y - p1.y) * (p3.x - p2.x) == (long long)(p3.y - p2.y) * (p2.x - p1.x);
}

int main() {
    int n;
    cin >> n;
    Point a[2000];
    for (int i = 0; i < n; ++i) {
        cin >> a[i].x >> a[i].y;
    }

    int count = 0;

    for (int i = 0; i < n; ++i) {
        unordered_map<long long, vector<int>> distMap;
        for (int j = 0; j < n; ++j) {
            if (i == j) continue;
            long long distSq = f(a[i], a[j]);
            distMap[distSq].push_back(j);
        }
        for (auto& pair : distMap) {
            const vector<int>& indices = pair.second;
            int m = indices.size();
            if (m >= 2) {
                for (int a = 0; a < m; ++a) {
                    for (int b = a + 1; b < m; ++b) {
                        int j = indices[a];
                        int k = indices[b];
                        if (!tt(a[i], a[j], a[k])) {
                            ++count;
                        }
                    }
                }
            }
        }
    }

    cout << count << endl;
    return 0;
}

• struct Point { int x, y; }; 定义了一个表示二维平面上点的结构体，包含两个整数 x`和 y，分别表示点的横坐标和纵坐标。

• long long f(const Point& p1, const Point& p2) 定义了一个函数，用于计算两点 p1 和 p2 之间的欧几里得距离的平方。这里使用了 long long 类型来存储结果，以避免整数溢出。

• bool tt(const Point& p1, const Point& p2, const Point& p3) 定义了一个函数，用于判断三点 p1、p2 和 p3 是否共线。共线性的判断依据是通过计算向量叉积：(p2.y - p1.y) * (p3.x - p2.x) == (p3.y - p2.y) * (p2.x - p1.x)。如果上述条件成立，则三点共线，函数返回 true，否则返回 false。

• 首先从标准输入读取点的数量 n。

• 然后定义了一个数组 a 来存储所有读取的点。

• 接下来读取 n 个点的坐标，存储到 a 数组中。

• 初始化计数器 count 为 0，用于记录不共线的三元组数量。

• 使用两层循环遍历每一对点，并计算它们之间的距离平方，存储在一个 unordered_map 中，其中键是距离平方，值是具有该距离平方的点的索引集合。

• 对于每个点 i，检查其与所有其他点的距离，并将距离相同的点索引分组。

• 如果某组具有相同距离的点数量大于等于 2，则从这组点中选择两个不同的点 j 和 k，与点 i 组成一个三元组 (i, j, k)。

• 使用 tt 函数判断该三元组是否共线。如果三点不共线，则计数器 count 增加。

• 最后，输出计数器 count 的值，表示不共线的三元组数量。

通过遍历所有点的组合，计算每组点之间的距离，并利用共线性判断函数来统计不共线的点三元组的数量，从而解决这个问题。