蓝桥杯每日真题 - 第12天
题目:(数三角)
题目描述(14届 C&C++ B组E题)

解题思路:
给定 n 个点的坐标,计算其中可以组成 等腰三角形 的三点组合数量。
-
核心条件:等腰三角形的定义是三角形的三条边中至少有两条边的长度相等。
-
坐标平面上的三点是否共线:如果三点共线,它们无法组成三角形。该程序在计算三点组合时,会排除共线的情况。
-
解决方案:对于每个点 i,计算它与其他点之间的距离,并将具有相同距离的点分组,保存在一个映射表(
map)中。随后从每组具有相同距离的点中,组合出两个点,构成一个等腰三角形。
代码实现(C++):
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
double dis(ll x1, ll y1, ll x2, ll y2){return pow((x1 - x2), 2) + pow((y1-y2),2);
}
bool check(pll p1, pll p2, pll p3){//判断是否三点共线if(p1.second == p2.second || p1.second == p3.second) return p1.second == p2.second && p1.second == p3.second;double a = (p1.first - p2.first) * 1.0 / (p1.second-p2.second);double b = (p1.first - p3.first) * 1.0 / (p1.second-p3.second);return abs(a - b) < 1e-6;
}
int main() {ll n; cin >> n;vector<pll> arr;for (int i = 0; i < n; ++i) {ll x, y;cin >> x >> y;arr.emplace_back(x, y);}ll ans = 0;//equ[i]存储的是第i个点所对应的map表//map表的含义是 有哪些点到第i个点的距离为key,这些点的下标用一个vector收集vector<map<double,vector<int>>> equ(n);for(int i = 0; i < n; ++i){auto m= equ[i];for(int j = 0; j < n; ++j){//遍历其他的所有点,在map中记录相等距离if(i != j){pll p1 = arr[i]; pll p2 = arr[j];double d = dis(p1.first,p1.second,p2.first,p2.second);m[d].push_back(j);}}//收集完成之后,遍历这张map表for(const auto& [k,v] : m){for(int a = 0; a < v.size(); ++a){ //从到当前点的距离相等的点之中选取两个点a,bfor(int b = a + 1; b < v.size(); ++b){if(!check(arr[i],arr[v[a]],arr[v[b]])){//只要不是三点共线ans++;}}}}}cout << ans;
}
得到运行结果:

代码分析:
-
距离计算:
dis函数计算两个点之间的欧几里得距离的平方,这样可以避免使用浮点运算。 -
三点共线判断:
check函数通过检查斜率是否相等来判断三点是否共线。通过分段计算和比较斜率来避免浮点数精度误差。 -
构建距离映射:对于每个点 iii,计算它到其他点的距离,并使用
map将这些距离相等的点分组。 -
等腰三角形组合计数:从距离相等的点中选择两个不同的点与当前点 iii 组合成三角形,检查是否共线。若不是共线,则计数增加。
难度分析
⭐️⭐️⭐️⭐️
总结
-
时间复杂度:该算法的复杂度为
,因为它使用三重循环来枚举所有三点组合。
-
空间复杂度:使用了
map来存储每个点到其他点的距离信息,相应的空间复杂度为。
相关文章:
蓝桥杯每日真题 - 第12天
题目:(数三角) 题目描述(14届 C&C B组E题) 解题思路: 给定 n 个点的坐标,计算其中可以组成 等腰三角形 的三点组合数量。 核心条件:等腰三角形的定义是三角形的三条边中至少有…...
从H264视频中获取宽、高、帧率、比特率等属性信息
背景 最近整理视频编解码的代码,早前在jetson上封装了jetson multimedia作为视频编解码的类,供其他同事和其他组使用,但该解码接口有一个问题,无法首先获取视频宽高信息,更无法直接获取视频的帧率、比特率等信息。 解…...
Cyberchef配合Wireshark提取并解析TCP/FTP流量数据包中的文件
前一篇文章中讲述了如何使用cyberchef提取HTTP/TLS数据包中的文件,详见《Cyberchef配合Wireshark提取并解析HTTP/TLS流量数据包中的文件》,链接这里,本文讲述下如何使用cyberchef提取FTP/TCP数据包中的文件。 FTP 是最为常见的文件传输协议,和HTTP协议不同的是FTP协议传输…...
Nginx中使用keepalive实现保持上游长连接实现提高吞吐量示例与测试
场景 HTTP1 .1之后协议支持持久连接,也就是长连接,优点在于在一个TCP连接上可以传送多个HTTP请求和响应, 减少了建立和关闭连接的消耗和延迟。 如果我们使用了nginx去作为反向代理或者负载均衡,从客户端过来的长连接请求就会被…...
深度学习-卷积神经网络CNN
案例-图像分类 网络结构: 卷积BN激活池化 数据集介绍 CIFAR-10数据集5万张训练图像、1万张测试图像、10个类别、每个类别有6k个图像,图像大小32323。下图列举了10个类,每一类随机展示了10张图片: 特征图计算 在卷积层和池化层结束后, 将特征…...
241114.学习日志——[CSDIY] [Cpp]零基础速成 [03]
CSDIY:这是一个非科班学生的努力之路,从今天开始这个系列会长期更新,(最好做到日更),我会慢慢把自己目前对CS的努力逐一上传,帮助那些和我一样有着梦想的玩家取得胜利!࿰…...
大模型研究报告 | 2024年中国金融大模型产业发展洞察报告|附34页PDF文件下载
随着生成算法、预训练模型、多模态数据分析等AI技术的聚集融合,AIGC技术的实践效用迎来了行业级大爆发。通用大模型技术的成熟推动了新一轮行业生产力变革,在投入提升与政策扶植的双重作用下,以大模型技术为底座、结合专业化金融能力的金融大…...
数据库SQL——什么是实体-联系模型(E-R模型)?
目录 什么是实体-联系模型? 1.实体集 2.联系集 3.映射基数 一对一(1:1) 一对多(1:n) 多对一(n:1) 多对多(m:n) 全部参与: 4.主码 弱实体集…...
在 MySQL 8.0 中,SSL 解密失败,在使用 SSL 加密连接时出现了问题
在 MySQL 8.0 中,SSL 解密失败通常指的是在使用 SSL 加密连接时出现了问题,导致无法建立加密通信。这个问题可能由多种原因引起,下面是一些常见的原因和排查方法: 1. 证书配置问题 确保您在 MySQL 配置中使用了正确的 SSL 证书和…...
React Native 全栈开发实战班 - 第四部分:用户界面进阶之动画效果实现
在移动应用中,动画效果 是提升用户体验的重要手段。合理的动画设计可以增强应用的交互性、流畅性和视觉吸引力。React Native 提供了多种实现动画的方式,包括内置的 Animated API、LayoutAnimation 以及第三方库(如 react-native-reanimated&…...
【CICD】GitLab Runner 和执行器(Executor
GitLab Runner 和执行器(Executor)是 GitLab CI/CD 管道中的两个重要组成部分。理解它们之间的关系有助于更好地配置和使用 CI/CD 流水线。runer是gitlab的ci-agent对接gitlab,而执行器是接受runer下发的ci的任务来干活的。也就是说gitrunner…...
实用教程:如何无损修改MP4视频时长
如何在UltraEdit中搜索MP4文件中的“mvhd”关键字 引言 在视频编辑和分析领域,有时我们需要深入到视频文件的底层结构中去。UltraEdit(UE)和UEStudio作为强大的文本编辑器,允许我们以十六进制模式打开和搜索MP4文件。本文将指导…...
mysqldump命令搭配source命令完成数据库迁移备份
mysqldump 命令使用 需保证mysqld在运行中, 这个命令的目的是将数据库导出到文件中,例如 mysqldump -uusername -ppassword database > db.sql 注意该命令不是在MySQL客户端(即MySQL命令行)执行的,而是在系统命…...
生信:TCGA学习(R、RStudio安装与下载、常用语法与常用快捷键)
前置环境 macOS系统,已安装homebrew且会相关命令。 近期在整理草稿区,所以放出该贴。 R语言、RStudio、R包安装 R语言安装 brew install rRStudio安装 官网地址:https://posit.co/download/rstudio-desktop/ R包下载 注意R语言环境自带…...
十三、注解配置SpringMVC
文章目录 1. 创建初始化类,代替web.xml2. 创建SpringConfig配置类,代替spring的配置文件3. 创建WebConfig配置类,代替SpringMVC的配置文件4. 测试功能 1. 创建初始化类,代替web.xml 2. 创建SpringConfig配置类,代替spr…...
为什么海外服务器IP会被封
海外服务器因为免备案而备受用户欢迎,近年来租用海外服务器的用户也越来越多,自然也可能会出现一些问题。 如果服务器IP被封,在该服务器下的所有业务都无法访问,对自己和对用户来说都会有较大的影响。因此,我们应做好相…...
图像处理技术椒盐噪声
椒盐噪声,也称为脉冲噪声,是图像中经常见到的一种噪声。它是一种随机出现的白点或者黑点,可能是亮的区域有黑色像素或是在暗的区域有白色像素(或是两者皆有)。这些白点和黑点会在图像中随机分布,导致图像中…...
[笔记]L6599的极限工作条件考量
0.名词 OTP over tempature protect.OCP over current protectOVP over voltage protectBrownout Protection Undervoltage Protection可能需要考虑hysteresis response.因为要考虑一些高频干扰 1.基本的过流保护逻辑 参考:ST L6599 器件手册 LLC开关电源&#…...
机器学习基础04
目录 1.朴素贝叶斯-分类 1.1贝叶斯分类理论 1.2条件概率 1.3全概率公式 1.4贝叶斯推断 1.5朴素贝叶斯推断 1.6拉普拉斯平滑系数 1.7API 2.决策树-分类 2.1决策树 2.2基于信息增益的决策树建立 2.2.1信息熵 2.2.2信息增益 2.2.3信息增益决策树建立步骤 2.3基于基…...
Ubuntu 20.04 配置开发环境(持续更新)
搜狗输入法不能显示中文 sudo apt install libqt5qml5 libgsettings-qt1 sudo apt install libqt5qml5 libqt5quick5 libqt5quickwidgets5 qml-module-qtquick2 编译环境配置 sudo apt-get update #base tools of ubuntu sudo apt install net-tools gitk tree vim termina…...
Linux应用开发之网络套接字编程(实例篇)
服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...
AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案
随着新能源汽车的快速普及,充电桩作为核心配套设施,其安全性与可靠性备受关注。然而,在高温、高负荷运行环境下,充电桩的散热问题与消防安全隐患日益凸显,成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...
鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南
1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发,使用DevEco Studio作为开发工具,采用Java语言实现,包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...
Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?
在大数据处理领域,Hive 作为 Hadoop 生态中重要的数据仓库工具,其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式,很多开发者常常陷入选择困境。本文将从底…...
Java编程之桥接模式
定义 桥接模式(Bridge Pattern)属于结构型设计模式,它的核心意图是将抽象部分与实现部分分离,使它们可以独立地变化。这种模式通过组合关系来替代继承关系,从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...
STM32HAL库USART源代码解析及应用
STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...
何谓AI编程【02】AI编程官网以优雅草星云智控为例建设实践-完善顶部-建立各项子页-调整排版-优雅草卓伊凡
何谓AI编程【02】AI编程官网以优雅草星云智控为例建设实践-完善顶部-建立各项子页-调整排版-优雅草卓伊凡 背景 我们以建设星云智控官网来做AI编程实践,很多人以为AI已经强大到不需要程序员了,其实不是,AI更加需要程序员,普通人…...
数据分析六部曲?
引言 上一章我们说到了数据分析六部曲,何谓六部曲呢? 其实啊,数据分析没那么难,只要掌握了下面这六个步骤,也就是数据分析六部曲,就算你是个啥都不懂的小白,也能慢慢上手做数据分析啦。 第一…...
大陆4D毫米波雷达ARS548调试
本文介绍了大陆ARS548毫米波雷达的调试与测试流程,主要包括以下内容: 设备参数:最大检测距离301m(可调93-1514m),支持gPTP时间同步。 接线调试: Windows需使用USB-RJ45转换器 Linux可直接连接网…...
