013几何数学——算法备赛
几何数学
平面切分
蓝桥杯2020年省赛题
问题描述
平面上有N条直线,其中第i条直线为y=Ax+B.请计算这些直线将平面分成了几个部分?
输入
第一行输入一个N,接下来N行输入两个整数代表Ai和Bi。
1<=N<=10^5.
思路分析
初始时一条直线将平面分为2个部分。
而后每添加一条直线
-
与前面某个直线重合,将平面多划分
0
个部分 -
与前面直线有
x
个交叉点,将平面多划分x+1
个部分。 -
与前面直线有
0
个交叉点,与前面直线平行,将平面多划分1
个部分
代码
#include <bits/stdc++.h>
using namespace std;
int main()
{int n; cin>>n;vector<pair<int,int>>d(n);for(int i=0;i<n;i++){cin>>d[i].first>>d[i].second;}long long ans=2; //初始时一条线将平面分为两个部分for(int i=1;i<n;i++){unordered_map<double,unordered_set<double>>mp; //mp[k]表示交叉点x=k的不同的y的集合auto [a,b]=d[i];bool vis=0;int s=0;for(int j=0;j<i;j++){ //对前面的线求交叉点auto [a1,b1]=d[j];if(a==a1){if(b!=b1){vis=true; //与前面线平行,寻找下一个continue;} else{s=-1; break; //与前面的线重叠}}double x=(double)(b-b1)/(a-a1); //交叉点xdouble y=(double)(a*b1-a1*b)/(a-a1); //交叉点yif(mp[x].count(y)) continue; //前面统计过这个交叉点,不重复统计else{s++;mp[x].insert(y);}}if(s) ans+=s+1;else ans+=vis; //没有新交叉点,与前面线平行}cout<<ans;return 0;
}
直线上最多的点
问题描述
给你一个数组 points
,其中 points[i] = [xi, yi]
表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。
原题链接
暴力枚举直线
我们知道,两点可以确定一条线。
一个朴素的做法是先枚举两点(确定一条线),然后检查其余点是否落在该线中。
为避免除法精度问题,当我们枚举两个点 x 和 y 时,不直接计算其对应直线的 斜率和 截距。
而是通过判断 x 和 y 与第三个点 p 形成的两条直线斜率是否相等,来得知点 p 是否落在该直线上。
详细说,当给定两个点 ( x 1 , y 1 ) 和 ( x 2 , y 2 ) 时,对应斜率 x 2 − x 1 y 2 − y 1 详细说,当给定两个点 (x_1 ,y_1) 和 (x_2,y_2) 时,对应斜率 \frac{x_2−x_1}{y_2-y_1} 详细说,当给定两个点(x1,y1)和(x2,y2)时,对应斜率y2−y1x2−x1
为避免计算机除法的精度问题,我们将判定 x 1 − x 2 y 1 − y 2 = x 2 − x 3 y 2 − y 3 改为判定 ( x 1 − x 2 ) ∗ ( y 2 − y 3 ) = ( x 2 − x 3 ) ∗ ( y 1 − y 2 ) 是否成立 为避免计算机除法的精度问题,我们将判定\frac{x_1-x_2}{y_1-y_2}=\frac{x_2-x_3}{y_2-y_3}改为判定(x_1-x_2)*(y_2-y_3)=(x_2-x_3)*(y_1-y_2)是否成立 为避免计算机除法的精度问题,我们将判定y1−y2x1−x2=y2−y3x2−x3改为判定(x1−x2)∗(y2−y3)=(x2−x3)∗(y1−y2)是否成立
这样一来,将存在精度问题的「除法判定」巧妙转为「乘法判定」。
时间复杂度O(n^3)
代码
class Solution {
public:int maxPoints(vector<vector<int>>& points) {int n = points.size(), ans = 1;for (int i = 0; i < n; i++) {vector<int> x = points[i];for (int j = i + 1; j < n; j++) {vector<int> y = points[j];// 枚举点对 (i,j) 并统计有多少点在该线上, 起始 cnt = 2 代表只有 i 和 j 两个点在此线上int cnt = 2;for (int k = j + 1; k < n; k++) {vector<int> p = points[k];int s1 = (y[1] - x[1]) * (p[0] - y[0]);int s2 = (p[1] - y[1]) * (y[0] - x[0]);if (s1 == s2) cnt++;}ans = max(ans, cnt);}}return ans;}
};
作者:宫水三叶
根据「朴素解法」的思路,枚举所有直线的过程不可避免,但统计点数的过程可以优化。
具体的,我们可以先枚举所有可能出现的 直线斜率(根据两点确定一条直线,即枚举所有的「点对」),使用「哈希表」统计所有 斜率 对应的点的数量,在所有值中取 max 即是答案。
一些细节:在使用「哈希表」进行保存时,为了避免精度问题,我们直接使用字符串进行保存,同时需要将 斜率 约干净。
int maxPoints(vector<vector<int>>& points) {int n = points.size(), ans = 1;for (int i = 0; i < n; i++) {unordered_map<string, int> map; //map放置在内层循环中,而不是全局的,固定一个点,保证平行的线不会统计到一起int maxv = 0;int x1 = points[i][0], y1 = points[i][1];for (int j = i + 1; j < n; j++) {int x2 = points[j][0], y2 = points[j][1];int a = x1 - x2, b = y1 - y2;int k = gcd(a, b);string key = to_string(a / k) + "_" + to_string(b / k); //无斜率直线为"0_1",斜率为0直线为"1_0"map[key]++;maxv = max(maxv, map[key]);}ans = max(ans, maxv + 1);}return ans;}int gcd(int a, int b) {return b ? gcd(b, a % b) : a;}
矩形面积
问题描述
给你 二维 平面上两个 由直线构成且边与坐标轴平行/垂直 的矩形,请你计算并返回两个矩形覆盖的总面积。
每个矩形由其 左下 顶点和 右上 顶点坐标表示:
- 第一个矩形由其左下顶点
(ax1, ay1)
和右上顶点(ax2, ay2)
定义。 - 第二个矩形由其左下顶点
(bx1, by1)
和右上顶点(bx2, by2)
定义。
原题链接
代码
int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {int sum1=(ax2-ax1)*(ay2-ay1);int sum2=(bx2-bx1)*(by2-by1);int x = max(0, min(ax2, bx2) - max(ax1, bx1)); //重叠的x轴长度int y = max(0, min(ay2, by2) - max(ay1, by1)); //重叠的y轴的长度return sum1+sum2-x1*x2; //总面积减重叠部分
}
在圆内生成随机点
问题描述
给定圆的半径和圆心的位置,实现函数 randPoint
,在圆中产生均匀随机点。
实现 Solution
类:
Solution(double radius, double x_center, double y_center)
用圆的半径radius
和圆心的位置(x_center, y_center)
初始化对象randPoint()
返回圆内的一个随机点。圆周上的一点被认为在圆内。答案作为数组返回[x, y]
。
原题链接
代码
class Solution {double r, x, y;Random random = new Random();public Solution(double _r, double _x, double _y) {r = _r; x = _x; y = _y;}public double[] randPoint() {double len = Math.sqrt(random.nextDouble(r * r)), ang = random.nextDouble(2 * Math.PI);double nx = x + len * Math.cos(ang), ny = y + len * Math.sin(ang);return new double[]{nx, ny};}
}作者:宫水三叶
相关文章:
013几何数学——算法备赛
几何数学 平面切分 蓝桥杯2020年省赛题 问题描述 平面上有N条直线,其中第i条直线为yAxB.请计算这些直线将平面分成了几个部分? 输入 第一行输入一个N,接下来N行输入两个整数代表Ai和Bi。 1<N<10^5. 思路分析 初始时一条直线将…...
VUE3:封装一个评论回复组件
之前用React封装的评论回复组件,里面有三个主要部分:CommentComponent作为主组件,CommentItem处理单个评论项,CommentInput负责输入框。现在需要将这些转换为Vue3的组件。 Vue3和React在状态管理上有所不同,Vue3使用r…...
DELL R740服务器闪黄灯不开机故障案例
1:DELL R740服务器 2:东莞长安客户工厂晚上十一二点电路跳闸多次,导致R740 ERP服务器无法开机。 3:故障现象为:主机能正常通电,开机按钮无通电迹象,正常情况会闪绿灯慢闪,通电一会后…...
记录一下QA(from deepseek)
Q1:__init__.py文件 在 Python 中,当你在一个目录下创建 __init__.py 文件时,这个目录会被视为一个 包(Package)。包的存在使得 Python 能够通过点号(.)层级式地组织模块(.py 文件)&…...
码蹄集——进制输出、求最大公约数、最小公倍数
进制乱炖 本题考查输出的进制转换,可以直接使用c里的format格式输出 #include<iostream> #include<algorithm> #include<string> using namespace std;int main() {int x;cin>>x;printf("%d %o %x %u\n",x,x,x,x);//十进制 八进…...
从技术走向管理:带来哪些角色转变与挑战
文章目录 一、从技术到管理1、从技术转到管理的优劣势(1)优势(2)劣势 2、刚转岗容易犯的几个问题3、最大的变化:不再是一个人单打独斗4、警惕:一开始不要把“人”过早的介入到“事”5、如何完成角色的转变&…...
C语言-指针(一)
目录 指针 内存 概念 指针变量 取地址操作符(&) 操作符“ * ” 指针变量的大小 注意 指针类型的意义 作用 void * 指针 const修饰指针变量 const放在*前 const放在*后 双重const修饰 指针的运算 1.指针 - 整数 2.指针 - 指针 3.指…...
Python面试问题
一、Python 基础 1. Python 的特点 动态类型:变量无需声明类型。解释型语言:逐行解释执行。支持多种编程范式(面向对象、函数式、过程式)。 2. 列表(List)与元组(Tuple)的区别 特…...
RAG工程-基于LangChain 实现 Advanced RAG(预检索优化)
Advanced RAG 概述 Advanced RAG 被誉为 RAG 的第二范式,它是在 Naive RAG 基础上发展起来的检索增强生成架构,旨在解决 Naive RAG 存在的一些问题,如召回率低、组装 prompt 时的冗余和重复以及灵活性不足等。它重点聚焦在检索增强࿰…...
【时时三省】(C语言基础)循环结构程序设计习题1
山不在高,有仙则名。水不在深,有龙则灵。 ----CSDN 时时三省 习题1 输入两个正整数m和n,求其最大公约数和最小公倍数。 解题思路: 求两个正整数 m 和 n 的最大公约数通常使用辗转相除法(欧几里得算法ÿ…...
[密码学实战]SDF之设备管理类函数(一)
[密码学实战]SDF之设备管理类函数(一) 一、标准解读:GM/T 0018-2023核心要求 1.1 SDF接口定位 安全边界:硬件密码设备与应用系统间的标准交互层功能范畴: #mermaid-svg-s3JXUdtH4erONmq9 {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16p…...
CDGP|如何建立高效的数据治理团队?
近年来,数据治理行业迅速发展,越来越多的企业开始重视并投入大量资源来建立和完善数据治理体系。数据治理体系不仅能够帮助企业更好地管理和利用数据资源,提升数据质量和数据价值,还能够为企业带来竞争优势和可持续发展能力。 然…...
如何评价 DeepSeek 的 DeepSeek-V3 模型?
DeepSeek-V3 是由杭州 DeepSeek 公司于 2024 年 12 月 26 日发布的一款开源大语言模型,其性能和创新技术在国内外引起了广泛关注。从多个方面来看,DeepSeek-V3 的表现令人印象深刻,具体评价如下: 性能卓越 DeepSeek-V3 拥有 6710 …...
【基础篇】prometheus命令行参数详解
文章目录 本篇内容讲解命令行参数详解 本篇内容讲解 prometheus高频修改命令行参数详解 命令行参数详解 在页面的/页面上能看到所有的命令行参数,如图所示: 使用shell命令查看 # ./prometheus --help usage: prometheus [<flags>]The Promethe…...
SpringBoot实现接口防刷的5种高效方案详解
目录 前言:接口防刷的重要性 方案一:基于注解的访问频率限制 实现原理 核心代码实现 使用示例 优缺点分析 方案二:令牌桶算法实现限流 算法原理 核心实现 配置使用 适用场景分析 方案三:分布式限流(Redis …...
DeepSearch复现篇:QwQ-32B ToolCall功能初探,以Agentic RAG为例
DeepSearch复现篇:QwQ-32B ToolCall功能初探,以Agentic RAG为例 作者:CyPaul Space 原文地址:https://zhuanlan.zhihu.com/p/30289363967 全文阅读约3分钟~ 背景 今天看到 论文:Search-R1: Training LLMs to Reason …...
项目实战-贪吃蛇大作战【补档】
这其实算是一个补档,因为这个项目是我在大一完成的,但是当时没有存档的习惯,今天翻以前代码的时候翻到了,于是乎补个档,以此怀念和志同道合的网友一起做项目的日子 ₍ᐢ ›̥̥̥ ༝ ‹̥̥̥ ᐢ₎♡ 这里面我主要负责…...
power bi获取局域网内共享文件
power bi获取局域网内共享文件 需求: 数据源并不一定都是在本地,有可能在云端,也有可能在其他服务器,今天分享如果数据源在另外一台服务器,如何获取数据源的方法。 明确需求:需要通过PowerBI获取局域网中的…...
100%提升信号完整性:阻抗匹配在高速SerDes中的实践与影响
一个高速信号SerDes通道(例如PCIe、112G/224G-PAM4)包含了这些片段: 传输线连通孔(PTH or B/B via)连接器高速Cable锡球(Ball and Bump) 我们会希望所有的片段都可以有一致的阻抗,…...
第六章:Tool and LLM Integration
Chapter 6: Tool and LLM Integration 从执行流到工具集成:如何让AI“调用真实世界的技能”? 在上一章的执行流框架中,我们已经能让多个代理协作完成复杂任务。但你是否想过:如果用户要求“查询实时天气”或“打开网页搜索”&…...
prompt提示词编写技巧
为什么学习prompt编写 目的:通过prompt的编写,提升LLM输出相关性、准确性和多样性,并对模型输出的格式进行限制,满足我们的业务需求。 学过提示词工程的人:像“专业导演”,通过精准指令控制 AI 输出&#…...
Nginx配置SSL详解
文章目录 Nginx配置SSL详解1. SSL/TLS 基础知识2. 准备工作3. 获取SSL证书4. Nginx SSL配置步骤4.1 基础配置4.2 配置说明 5. 常见配置示例5.1 双向认证配置5.2 多域名SSL配置 6. 安全优化建议7. 故障排查总结参考资源下载验证的完整实例 Nginx配置SSL详解 1. SSL/TLS 基础知识…...
网络安全之红队LLM的大模型自动化越狱
前言 大型语言模型(LLMs)已成为现代机器学习的重要支柱,广泛应用于各个领域。通过对大规模数据的训练,这些模型掌握了多样化的技能,展现出强大的生成与理解能力。然而,由于训练数据中难以完全剔除有毒内容&…...
【技术笔记】通过Cadence Allegro创建一个PCB封装(以SOT23为例)
【技术笔记】通过Cadence Allegro创建一个PCB封装(以SOT23为例) 一、焊盘创建二、PCB封装设计三、丝印位号及标识添加 更多内容见专栏:【硬件设计遇到了不少问题】、【Cadence从原理图到PCB设计】 一、焊盘创建 首先要找到元器件的相关手册&…...
新环境注册为Jupyter 内核
1. 确认环境是否已注册为内核 在终端运行以下命令,查看所有已注册的内核: jupyter kernelspec list2. 为自定义环境注册内核 步骤 1:激活目标虚拟环境 conda activate your_env_name # 替换为你的环境名步骤 2:安装…...
[Spring] Seata详解
🌸个人主页:https://blog.csdn.net/2301_80050796?spm1000.2115.3001.5343 🏵️热门专栏: 🧊 Java基本语法(97平均质量分)https://blog.csdn.net/2301_80050796/category_12615970.html?spm1001.2014.3001.5482 🍕 Collection与…...
使用JDK的数据校验和Spring的自定义注解校验前端传递参数的两种方法
第一种:JDK的数据校验注解 PostMapping("/test")public String test(QueryParam param, RequestHeader(value "App_key") String App_key,RequestHeader(value "App_secret") String App_secret) throws IOException {param.setApp…...
JS错误处理的新方案 (不使用try-catch)
错误处理一直是JavaScript开发者需要认真对待的问题,传统的try-catch语法虽然简单直观,但在异步代码中使用时存在诸多限制。 try-catch的局限性 传统try-catch模式在现代JavaScript开发中面临的问题: 1. 异步错误捕获的缺陷 try-catch无法…...
前端实现商品放大镜效果(Vue3完整实现)
前端实现商品放大镜效果(Vue3完整实现) 前言 在电商类项目中,商品图片的细节展示至关重要。放大镜效果能显著提升用户体验,允许用户在不跳转页面的情况下查看高清细节。本文将基于Vue3实现一个高性能的放大镜组件,完整…...
redis未授权访问漏洞学习
一、Redis常见用途 1. Redis介绍 全称与起源: Redis全称Remote Dictionary Service(远程字典服务),最初由antirez在2009年开发,用于解决网站访问记录统计的性能问题。发展历程: 从最初仅支持列表功能的内存数据库,经过十余年发展已支持多种…...
阿里qiankun微服务搭建
主服务 chat vue3 ts vite 子服务 ppt react 18 vite 子服务 agent 主服务 npm i vite-plugin-qiankun mian.ts import ./style/base.scss import virtual:svg-icons-register import { createApp } from vue import { createPinia } from piniaimport App from ./App.vue im…...
【CodeSprint】第二章-2.1 简单模拟
第二章 2.1 简单模拟 ✏️ 关于专栏:专栏用于记录 prepare for the coding test。 1. 简单模拟 简单模拟题目不需要复杂算法,直接按照题意一步步模拟即可。 1.1 促销计算 题目描述 某百货公司为了促销,采用购物打折的优惠方法:…...
Golang实现函数默认参数
golang原生不支持默认参数 在日常开发中,我们有时候需要使用默认设置,但有时候需要提供自定义设置 结构体/类,在Java我们可以使用无参、有参构造函数来实现,在PHP中我们也可以实现(如 public function xxx($isCName false, $sec…...
【Python Web开发】03-HTTP协议
文章目录 1. HTTP协议基础1.1 请求-响应模型1.2 请求方法1.3 请求和响应结构1.4 状态码 2. Python 发送 HTTP 请求2.1 urllib库2.2 requests 库 3. Python 构建 HTTP 服务器3.1 http.server模块3.2 Flask 框架 4. HTTP 协议的安全问题5. 缓存和性能优化 HTTP(Hypert…...
提高营销活动ROI:大数据驱动的精准决策
提高营销活动ROI:大数据驱动的精准决策 大家好,我是Echo_Wish。今天我们来聊聊如何通过大数据来提高营销活动的ROI(投资回报率)。我们都知道,随着市场的日益竞争,营销的成本不断增加,如何在这片红海中脱颖而出,不仅需要精准的营销策略,还需要依靠先进的技术,尤其是大…...
前端excel导出
在数据可视化和管理日益重要的今天,前端实现 Excel 导出功能已经成为众多项目中的刚需。 一、Excel 导出的常见场景 数据报表导出:在企业管理系统、数据分析平台中,用户经常需要将系统中的数据以 Excel 表格的形式导出,便于离…...
pymsql(SQL注入与防SQL注入)
SQL注入: import pymysql# 创建数据库连接 返回一个对象 conn pymysql.connect(host"localhost", # MySQL服务器地址 本地地址 127.0.0.1user"root", # 用户名 (账号)password"155480", # 密码database&qu…...
基于Springboot + vue + 爬虫实现的高考志愿智能推荐系统
项目描述 本系统包含管理员和学生两个角色。 管理员角色: 个人中心管理:管理员可以管理自己的个人信息。 高校信息管理:管理员可以查询、添加或删除高校信息,并查看高校详细信息。 学生管理:管理员可以查询、添加或…...
delphi使用sqlite3
看了一下delphi调用sqlite3最新版本的调用,网上说的都很片面,也没有完整的资料了。 我自己研究了一下,分享出来。 在调用demo中,官方也给了一个demo但是功能很少,没有参考价值。 1.定义: 首先把sqlite3…...
高压开关柜局部放电信号分析系统
高压开关柜局部放电信号分析系统 - 开发笔记 1. 项目概述 这个项目是我在2025年实现的高压开关柜局部放电信号分析系统,目的是通过采集分析局部放电信号,判断设备的工作状态和潜在故障。系统包含从信号模拟生成、特征提取、到深度学习模型训练的全流程…...
ai环境conda带torch整体迁移。
conda打包好的GPU版torch环境,其实很简单,就是conda装好的torch环境env整体打包,然后到新机器上再解压到env路径。 打开搭建好的环境,找自己路径,我默认的是这个。 cd/root/anaconda3/envs/ 然后整个文件夹打包。tar -…...
电价单位解析与用电设备耗电成本计算
一、电价单位 元/kWh 的解析 定义: 元/kWh 表示每千瓦时电能的费用,即1度电的价格。例如,若电价为0.5元/kWh,则使用1千瓦的电器1小时需支付0.5元。 电价构成: 中国销售电价由四部分组成: 上网电价…...
辛格迪客户案例 | 华道生物细胞治疗生产及追溯项目(CGTS)
01 华道(上海)生物医药有限公司:细胞治疗领域的创新先锋 华道(上海)生物医药有限公司(以下简称“华道生物”)是一家专注于细胞治疗技术研发与应用的创新型企业,尤其在CAR-T细胞免疫…...
C++(初阶)(十三)——继承
继承 继承概念示例 定义格式 继承和访问方式继承方式访问方式实例 继承类模板基类和派生类之间的转换继承中的作用域隐藏规则选择题 派生类的默认成员函数默认成员函数派生类中的实现 实现一个不能被继承的类继承与友元继承与静态成员多继承及其菱形继承问题虚继承多继承指针偏…...
S09-电机运行时间
感谢粉丝网友的支持,也欢迎你们的讨论和分享。昨天我们简单讨论了一下标准功能块的重要性,仅仅是拿电机块举了一个例子,有粉丝问能否把电机运行时间做到块里面,完善一下功能呢?那是绝对当然的100%可以的啊!…...
大语言模型(LLMs)微调技术总结
文章目录 全面总结当前大语言模型(LLM)微调技术1. 引言2. 为什么需要微调?3. 微调技术分类概览4. 各种微调技术详细介绍4.1 基础微调方法4.1.1 有监督微调(Supervised Fine-Tuning, SFT)4.1.2 全参数微调(F…...
python练习:求数字的阶乘
求数字的阶乘 eg:5的阶乘 54321 """ 求数字的阶乘 eg:5的阶乘 5*4*3*2*1 """count 1 for i in range(1,6):count count * iprint(count)运行结果:...
综合练习一
背景 某银行监管系统,需要设计并实现用户登入记录功能,每个用户登入系统时,系统自动记录登入用户的账户、登入时间、登入失败成功与否信息等,普通用户只能登入登出,管理员可以登入后查看日志及分析统计信息等。 用户…...
List--链表
一、链表 1.1 什么是List? 在C语言中,我们需要使用结构体struct来进行List(链表)的实现: struct ListNode {DataType Data;//DataType是任意类型的变量定义struct ListNode* next;//指向下一个结点的指针变量 }; 与之前的vect…...
SpeedyAutoLoot
SpeedyAutoLoot自动拾取插件 SpeedyAutoLoot.lua local AutoLoot CreateFrame(Frame)SpeedyAutoLootDB SpeedyAutoLootDB or {} SpeedyAutoLootDB.global SpeedyAutoLootDB.global or {}local BACKPACK_CONTAINER BACKPACK_CONTAINER local LOOT_SLOT_CURRENCY LOOT_SLOT…...