蓝桥杯每日真题 - 第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…...
华为云AI开发平台ModelArts
华为云ModelArts:重塑AI开发流程的“智能引擎”与“创新加速器”! 在人工智能浪潮席卷全球的2025年,企业拥抱AI的意愿空前高涨,但技术门槛高、流程复杂、资源投入巨大的现实,却让许多创新构想止步于实验室。数据科学家…...
Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...
微信小程序 - 手机震动
一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注:文档 https://developers.weixin.qq…...
屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!
5月28日,中天合创屋面分布式光伏发电项目顺利并网发电,该项目位于内蒙古自治区鄂尔多斯市乌审旗,项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站,总装机容量为9.96MWp。 项目投运后,每年可节约标煤3670…...
华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)
宇树机器人多姿态起立控制强化学习框架论文解析 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一) 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...
GC1808高性能24位立体声音频ADC芯片解析
1. 芯片概述 GC1808是一款24位立体声音频模数转换器(ADC),支持8kHz~96kHz采样率,集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器,适用于高保真音频采集场景。 2. 核心特性 高精度:24位分辨率,…...
关键领域软件测试的突围之路:如何破解安全与效率的平衡难题
在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件,这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下,实现高效测试与快速迭代?这一命题正考验着…...
Golang——9、反射和文件操作
反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一:使用Read()读取文件2.3、方式二:bufio读取文件2.4、方式三:os.ReadFile读取2.5、写…...
