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

题目描述

小明在二维坐标系中放置了 $n$ 个点，他想在其中选出一个包含三个点的子集，这三个点能组成三角形。然而这样的方案太多了，他决定只选择那些可以组成等腰三角形的方案。请帮他计算出一共有多少种选法可以组成等腰三角形？

输入格式

输入共 $n+1$ 行。

第一行为一个正整数 $n$。

后面 $n$ 行，每行两个整数 $x_i,y_i$ 表示第 $i$ 个点的坐标。

输出格式

输出共 $1$ 行，一个整数。

输入输出样例 #1

输入 #1

5
1 4
1 0
2 1
1 2
0 1

输出 #1

5

说明/提示

样例说明

一共有 $5$ 种选法：{2,3,4}\{2,3,4\}{2,3,4}、{3,4,5}\{3,4,5\}{3,4,5}、{4,5,2}\{4,5,2\}{4,5,2}、{5,2,3}\{5,2,3\}{5,2,3}、{1,3,5}\{1,3,5\}{1,3,5}。

评测用例规模与约定

• 对于 $20\%$ 的数据，保证 $n\le 200$。
• 对于 $100\%$ 的数据，保证 $n\le 2000$，$0\le x_i,y_i\le 10^9$。

第十四届蓝桥杯大赛软件赛决赛 C/C++ 大学 B 组 E 题

C++实现

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <utility>
#include <map>
using ll = long long int;
using pii = std::pair <int, int>;
const int MAXN = 2e3 + 10;
int n, ans;
std::map <ll, int> dist;
std::map <pii, int> mp;
pii node[MAXN];
ll getdist (int a, int b) {
    int x1 = node[a].first, y1 = node[a].second, x2 = node[b].first, y2 = node[b].second;
    return 1ll * (x2 - x1) * (x2 - x1) + 1ll * (y2 - y1) * (y2 - y1);
}
pii getmid (pii a, pii b) {
    if ((a.first + b.first & 1) || (a.second + b.second & 1))
        return {-1, -1};
    else return {a.first + b.first >> 1, a.second + b.second >> 1};
}
ll C (int n, int m) { // it seems that m cannot be greater than 2.
    if (m == 1) return n;
    else if (m == 2) return n * (n - 1) / 2;
}
int main () {
    std::cin >> n;
    for (int i = 1; i <= n; i++) {
        std::cin >> node[i].first >> node[i].second;
        mp[node[i]]++;
    }
    for (int i = 1; i <= n; i++) {
        dist.clear();
        for (int j = 1; j <= n; j++) {
            if (i == j) continue;
            dist[getdist(i, j)]++;
        }
        for (auto [d, cnt] : dist)
            ans += C(cnt, 2);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++)
            ans -= mp[getmid(node[i], node[j])];
    }
    std::cout << ans;
    return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容