当前位置: 首页 > news >正文

蓝桥杯每日真题 - 第12天

题目:(数三角)

题目描述(14届 C&C++ B组E题)

解题思路:

给定 n 个点的坐标,计算其中可以组成 等腰三角形 的三点组合数量。

  1. 核心条件:等腰三角形的定义是三角形的三条边中至少有两条边的长度相等。

  2. 坐标平面上的三点是否共线:如果三点共线,它们无法组成三角形。该程序在计算三点组合时,会排除共线的情况。

  3. 解决方案:对于每个点 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 组合成三角形,检查是否共线。若不是共线,则计数增加。

难度分析

⭐️⭐️⭐️⭐️

总结

  • 时间复杂度:该算法的复杂度为 O\left ( n^{3} \right ),因为它使用三重循环来枚举所有三点组合。

  • 空间复杂度:使用了 map 来存储每个点到其他点的距离信息,相应的空间复杂度为 O\left ( n^{2} \right )

相关文章:

蓝桥杯每日真题 - 第12天

题目&#xff1a;&#xff08;数三角&#xff09; 题目描述&#xff08;14届 C&C B组E题&#xff09; 解题思路&#xff1a; 给定 n 个点的坐标&#xff0c;计算其中可以组成 等腰三角形 的三点组合数量。 核心条件&#xff1a;等腰三角形的定义是三角形的三条边中至少有…...

从H264视频中获取宽、高、帧率、比特率等属性信息

背景 最近整理视频编解码的代码&#xff0c;早前在jetson上封装了jetson multimedia作为视频编解码的类&#xff0c;供其他同事和其他组使用&#xff0c;但该解码接口有一个问题&#xff0c;无法首先获取视频宽高信息&#xff0c;更无法直接获取视频的帧率、比特率等信息。 解…...

Cyberchef配合Wireshark提取并解析TCP/FTP流量数据包中的文件

前一篇文章中讲述了如何使用cyberchef提取HTTP/TLS数据包中的文件,详见《Cyberchef配合Wireshark提取并解析HTTP/TLS流量数据包中的文件》,链接这里,本文讲述下如何使用cyberchef提取FTP/TCP数据包中的文件。 FTP 是最为常见的文件传输协议,和HTTP协议不同的是FTP协议传输…...

Nginx中使用keepalive实现保持上游长连接实现提高吞吐量示例与测试

场景 HTTP1 .1之后协议支持持久连接&#xff0c;也就是长连接&#xff0c;优点在于在一个TCP连接上可以传送多个HTTP请求和响应&#xff0c; 减少了建立和关闭连接的消耗和延迟。 如果我们使用了nginx去作为反向代理或者负载均衡&#xff0c;从客户端过来的长连接请求就会被…...

深度学习-卷积神经网络CNN

案例-图像分类 网络结构: 卷积BN激活池化 数据集介绍 CIFAR-10数据集5万张训练图像、1万张测试图像、10个类别、每个类别有6k个图像&#xff0c;图像大小32323。下图列举了10个类&#xff0c;每一类随机展示了10张图片&#xff1a; 特征图计算 在卷积层和池化层结束后, 将特征…...

241114.学习日志——[CSDIY] [Cpp]零基础速成 [03]

​ CSDIY&#xff1a;这是一个非科班学生的努力之路&#xff0c;从今天开始这个系列会长期更新&#xff0c;&#xff08;最好做到日更&#xff09;&#xff0c;我会慢慢把自己目前对CS的努力逐一上传&#xff0c;帮助那些和我一样有着梦想的玩家取得胜利&#xff01;&#xff0…...

大模型研究报告 | 2024年中国金融大模型产业发展洞察报告|附34页PDF文件下载

随着生成算法、预训练模型、多模态数据分析等AI技术的聚集融合&#xff0c;AIGC技术的实践效用迎来了行业级大爆发。通用大模型技术的成熟推动了新一轮行业生产力变革&#xff0c;在投入提升与政策扶植的双重作用下&#xff0c;以大模型技术为底座、结合专业化金融能力的金融大…...

数据库SQL——什么是实体-联系模型(E-R模型)?

目录 什么是实体-联系模型&#xff1f; 1.实体集 2.联系集 3.映射基数 一对一&#xff08;1:1&#xff09; 一对多&#xff08;1:n&#xff09; 多对一&#xff08;n:1&#xff09; 多对多&#xff08;m:n&#xff09; 全部参与&#xff1a; 4.主码 弱实体集&#xf…...

在 MySQL 8.0 中,SSL 解密失败,在使用 SSL 加密连接时出现了问题

在 MySQL 8.0 中&#xff0c;SSL 解密失败通常指的是在使用 SSL 加密连接时出现了问题&#xff0c;导致无法建立加密通信。这个问题可能由多种原因引起&#xff0c;下面是一些常见的原因和排查方法&#xff1a; 1. 证书配置问题 确保您在 MySQL 配置中使用了正确的 SSL 证书和…...

React Native 全栈开发实战班 - 第四部分:用户界面进阶之动画效果实现

在移动应用中&#xff0c;动画效果 是提升用户体验的重要手段。合理的动画设计可以增强应用的交互性、流畅性和视觉吸引力。React Native 提供了多种实现动画的方式&#xff0c;包括内置的 Animated API、LayoutAnimation 以及第三方库&#xff08;如 react-native-reanimated&…...

【CICD】GitLab Runner 和执行器(Executor

GitLab Runner 和执行器&#xff08;Executor&#xff09;是 GitLab CI/CD 管道中的两个重要组成部分。理解它们之间的关系有助于更好地配置和使用 CI/CD 流水线。runer是gitlab的ci-agent对接gitlab&#xff0c;而执行器是接受runer下发的ci的任务来干活的。也就是说gitrunner…...

实用教程:如何无损修改MP4视频时长

如何在UltraEdit中搜索MP4文件中的“mvhd”关键字 引言 在视频编辑和分析领域&#xff0c;有时我们需要深入到视频文件的底层结构中去。UltraEdit&#xff08;UE&#xff09;和UEStudio作为强大的文本编辑器&#xff0c;允许我们以十六进制模式打开和搜索MP4文件。本文将指导…...

mysqldump命令搭配source命令完成数据库迁移备份

mysqldump 命令使用 需保证mysqld在运行中&#xff0c; 这个命令的目的是将数据库导出到文件中&#xff0c;例如 mysqldump -uusername -ppassword database > db.sql 注意该命令不是在MySQL客户端&#xff08;即MySQL命令行&#xff09;执行的&#xff0c;而是在系统命…...

生信:TCGA学习(R、RStudio安装与下载、常用语法与常用快捷键)

前置环境 macOS系统&#xff0c;已安装homebrew且会相关命令。 近期在整理草稿区&#xff0c;所以放出该贴。 R语言、RStudio、R包安装 R语言安装 brew install rRStudio安装 官网地址&#xff1a;https://posit.co/download/rstudio-desktop/ R包下载 注意R语言环境自带…...

十三、注解配置SpringMVC

文章目录 1. 创建初始化类&#xff0c;代替web.xml2. 创建SpringConfig配置类&#xff0c;代替spring的配置文件3. 创建WebConfig配置类&#xff0c;代替SpringMVC的配置文件4. 测试功能 1. 创建初始化类&#xff0c;代替web.xml 2. 创建SpringConfig配置类&#xff0c;代替spr…...

为什么海外服务器IP会被封

海外服务器因为免备案而备受用户欢迎&#xff0c;近年来租用海外服务器的用户也越来越多&#xff0c;自然也可能会出现一些问题。 如果服务器IP被封&#xff0c;在该服务器下的所有业务都无法访问&#xff0c;对自己和对用户来说都会有较大的影响。因此&#xff0c;我们应做好相…...

图像处理技术椒盐噪声

椒盐噪声&#xff0c;也称为脉冲噪声&#xff0c;是图像中经常见到的一种噪声。它是一种随机出现的白点或者黑点&#xff0c;可能是亮的区域有黑色像素或是在暗的区域有白色像素&#xff08;或是两者皆有&#xff09;。这些白点和黑点会在图像中随机分布&#xff0c;导致图像中…...

[笔记]L6599的极限工作条件考量

0.名词 OTP over tempature protect.OCP over current protectOVP over voltage protectBrownout Protection Undervoltage Protection可能需要考虑hysteresis response.因为要考虑一些高频干扰 1.基本的过流保护逻辑 参考&#xff1a;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面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

Admin.Net中的消息通信SignalR解释

定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

多模态大语言模型arxiv论文略读(108)

CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题&#xff1a;CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者&#xff1a;Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...

ios苹果系统,js 滑动屏幕、锚定无效

现象&#xff1a;window.addEventListener监听touch无效&#xff0c;划不动屏幕&#xff0c;但是代码逻辑都有执行到。 scrollIntoView也无效。 原因&#xff1a;这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作&#xff0c;从而会影响…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点&#xff1a; 多级缓存&#xff0c;先查本地缓存&#xff0c;再查Redis&#xff0c;最后才查数据库热点数据重建逻辑使用分布式锁&#xff0c;二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...