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

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

code：

CPP

#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$ 的值，表示不共线的三元组数量。

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

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

文章操作

code：

相关推荐

评论

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