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

HAO的Graham学习笔记

news 来源：原创 2025/5/16 13:35:38

前置知识：凸包

摘录oiwiki

在平面上能包含所有给定点的最小凸多边形叫做凸包。
其定义为：对于给定集合 X，所有包含 X 的凸集的交集 S 被称为 X 的凸包。

说人话就是用一个橡皮筋包含住所有给定点的形态

如图：这就是土包

正题：Graham求凸包

过程

Graham求凸包的过程是：
1，选一个点，其它点以它作为标准将其他点进行极角排序
两种方法，建议使用atan2(懒)
atan2用法：atan2(横坐标，纵坐标）（注：以选择的点为原点的坐标）

2，从最低的点开始（这能保证第一个点一定在凸包内）枚举
分成两种情况：

if 上一个点在这个点的左边{将这个点加入答案
}
else{将这个点pop
}

此处可用叉积判断左右，叉积学习
3，连接第一个点与最后一个点
分析时间复杂度
处理时每个点只会一次，即为O(n),n为点数，还有角排序的O(nlog(n)),总体为O(n+nlog(n))

实例

如果下一个点在右边像这样就这样
(原应从第一个点连了第二点后直接连最右下的点，但我这画错了，致歉）
很明显，将上一个点排出，因为当前的点劣于当前点（当前点在上个点右边）

变成了这样
在这里插入图片描述
发现当前的点还是优于最后一个点（在其右），排出 Graham
在上一点的左边，加入
其它的都在左边不在赘述
结果就是：

有一个很好的演示视频，放在这（看了就去支持那个up吧，sto颓废orz）
演示视频

代码实现

模版

First,初始化每个点的极角度数（此处为atan2实现）

	//p是存点的，x是行，y是列，与平面直角坐标系完全相反//p[1]是最低的点，以p[1]为原点for(int i=1;i<=n;i++){p[i].angle=atan2(p[i].x-p[1].x,p[i].y-p[1].y);}

Second,排序（以极角排(大的先)，相同就以在p[1]右来排序）

bool cmp(node x,node y){if(x.angle==y.angle){return ju(x,p[1])>ju(y,p[1]);}return x.angle>y.angle;
}

Third 开始处理（以单调栈维护答案）

	st[++top]=p[1];for(int i=2;i<=n;i++){while(top>=2&&jiao(st[top]-st[top-1],p[i]-st[top])<0){top--;}st[++top]=p[i];}st[top+1]=p[1];

完整代码
这个代码是P2742的，凸包模版题
请勿 Ctrl-A+Ctrl-C+Ctrl-V 丝滑小连招，请自己了解后手打一遍

#include<bits/stdc++.h>
using namespace std;
struct node{double x,y;double angle;node operator-(const node p)const{return{x-p.x,y-p.y,0};}
}p[100001];
int n;
int s1[10001];
double ju(node x,node y){//求距离 return sqrt((x.y-y.y)*(x.y-y.y)+(y.x-x.x)*(y.x-x.x));
}
bool cmp(node x,node y){//角排序 if(x.angle==y.angle){return ju(x,p[1])>ju(y,p[1]);}return x.angle>y.angle;
}
double jiao(node x,node y){//叉积 return x.x*y.y-x.y*y.x;
}
node st[100001];
int top;
int main(){cin>>n;int k,xx,yy;for(int i=1;i<=n;i++){cin>>p[i].y>>p[i].x;if(i==1){k=i;xx=p[i].x;yy=p[i].y;}if(p[i].x<xx||(p[i].x==xx&&p[i].y<yy)){k=i;xx=p[i].x;yy=p[i].y;}}swap(p[k],p[1]);for(int i=1;i<=n;i++){p[i].angle=atan2(p[i].x-p[1].x,p[i].y-p[1].y);}sort(p+2,p+n+1,cmp);st[++top]=p[1];for(int i=2;i<=n;i++){while(top>=2&&jiao(st[top]-st[top-1],p[i]-st[top])<0){top--;}st[++top]=p[i];}st[top+1]=p[1];double ans=0;for(int i=1;i<=top;i++){ans+=ju(st[i],st[i+1]);
//		cout<<st[i].x<<" "<<st[i].y<<endl;}printf("%.2lf",ans);
}

例题：P3829

题意：给你一堆给出的卡片，求其凸包周长（凸包长度包含圆弧长度）
分析第三个样例：

其中的黑色凸包与答案红色部分的长度完全相同，在根据我们小学8年级的知识：多变形的外角和为360度，所以外面的圆弧刚好就是一个圆，答案就等于凸包+一个圆的长度。
代码：我不贴了

预告

可能会出Andrew的笔记，那时会用Andrew写一遍P3829

HAO的Graham学习笔记

前置知识：凸包摘录oiwiki 在平面上能包含所有给定点的最小凸多边形叫做凸包。其定义为：对于给定集合 X，所有包含 X 的凸集的交集 S 被称为 X 的凸包。说人话就是用一个橡皮筋包含住所有给定点的形态如图： 正题&#xff1a…...

编程日记 2025/5/16 13:35:38

C#基础知识

0 C#介绍定义与背景 C#（发音为C - sharp）是微软公司开发的一种高级编程语言。它是专门为构建在微软的.NET平台上运行的各种应用程序而设计的。在2000年左右推出，目的是结合当时编程语言的优点，如C的强大功能和Java的简单性与安全…...

编程日记 2025/5/13 0:12:39

Kafka中文文档

文章来源：https://kafka.cadn.net.cn 什么是事件流式处理？ 事件流是人体中枢神经系统的数字等价物。它是为“永远在线”的世界奠定技术基础，在这个世界里，企业越来越多地使用软件定义和 automated，而软件的用户更…...

编程日记 2025/5/14 22:40:30

Tyrant(暴君):反向Shell-后门注入与持久化控制的渗透测试工具

Tyrant Tyrant 是一款用于渗透测试和远程控制持久化的恶意工具，具备以下功能： 反向Shell：允许攻击者通过指定用户UID进行反弹对应权限的Shell会话。后门注入与持久化：在目标系统中注入后门并确保即使重启后依然能恢复控制。Tyran…...

编程日记 2025/5/15 4:00:39

leetcode刷题-贪心04

代码随想录贪心算法part04|452. 用最少数量的箭引爆气球、435. 无重叠区间、763.划分字母区间 452. 用最少数量的箭引爆气球435. 无重叠区间763.划分字母区间今天的三道题目，都算是重叠区间问题，大家可以好好感受一下。都属于那种看起来好复杂&#…...

编程日记 2025/5/15 17:37:59

系统学习算法：专题八二叉树中的深搜

深搜其实就是深度优先遍历（dfs），与此相对的还有宽度优先遍历（bfs） 如果学完数据结构有点忘记，如下图，左边是dfs，右边是bfs 而二叉树的前序，中序，后序遍历都可…...

编程日记 2025/5/16 13:26:14

2022年全国职业院校技能大赛网络系统管理赛项模块A：网络构建（样题2）-网络部分解析-附详细代码

目录附录1：拓扑图编辑附录2：地址规划表 1.SW1 2.SW2 3.SW3 4.SW4 5.SW5 6.SW6 7.SW7 8.R1 9.R2 10.R3 11.AC1 12.AC2 13.EG1 14.EG2 15.AP2 16.AP3 附录1：拓扑图附录2：地址规划表...

编程日记 2025/5/13 3:16:45

笔试-业务逻辑4

应用小明在玩一个数字加减游戏，输入4个正整数：s、t、a、b，其中s>1，b<105，a!b。只使用加法或者减法，使得st。每回合，小明用当前的数字，加上或减去一个数字；目前有…...

编程日记 2025/5/14 20:11:23

冷启动+强化学习：DeepSeek-R1 的原理详解——无需监督数据的推理能力进化之路

本文基于 DeepSeek 官方论文进行分析，论文地址为：https://github.com/deepseek-ai/DeepSeek-R1/blob/main/DeepSeek_R1.pdf 有不足之处欢迎评论区交流原文翻译在阅读和理解一篇复杂的技术论文时，逐字翻译是一个重要的步骤。它不仅能帮助我们准确把握作者的原意，还能为后续…...

编程日记 2025/5/13 9:24:13

ubuntu22安装issac gym记录

整体参考：https://blog.csdn.net/Yakusha/article/details/144306858 安装完成后的整体版本信息 ubuntu：22.04内核：6.8.0-51-generic显卡：NVIDIA GeForce RTX 3050 OEM显卡驱动：535.216.03cuda：12.2cudnn&…...

编程日记 2025/5/12 10:30:15

Docker小游戏 | 使用Docker部署2048网页小游戏

Docker小游戏 | 使用Docker部署2048网页小游戏前言项目介绍项目简介项目预览二、系统要求环境要求环境检查Docker版本检查检查操作系统版本三、部署2048网页小游戏下载镜像创建容器检查容器状态检查服务端口安全设置四、访问2048网页小游戏五、总结前言在当今快速发展的技术世…...

编程日记 2025/5/15 6:08:12

C基础寒假练习(2)

一、输出3-100以内的完美数，(完美数：因子和(因子不包含自身)数本身 #include <stdio.h>// 函数声明 int isPerfectNumber(int num);int main() {printf("3-100以内的完美数有:\n");for (int i 3; i < 100; i){if (isPerfectNumber…...

编程日记 2025/5/12 6:30:44

传输层协议 UDP 与 TCP

🌈 个人主页：Zfox_ 🔥 系列专栏：Linux 目录一：🔥 前置复盘🦋 传输层🦋 再谈端口号🦋 端口号范围划分🦋 认识知名端口号 (Well-Know Port Number) 二&#xf…...

编程日记 2025/5/13 3:15:01

Vue06

目录一、声明式导航-导航链接 1.需求 2.解决方案 3.通过router-link自带的两个样式进行高亮二、声明式导航的两个类名 1.router-link-active 2.router-link-exact-active 三、声明式导航-自定义类名（了解） 1.问题 2.解决方案 3.代码演示四…...

编程日记 2025/5/13 17:02:56

AJAX笔记进阶篇

黑马程序员视频地址： AJAX-Day04-01.同步代码和异步代码https://www.bilibili.com/video/BV1MN411y7pw?vd_source0a2d366696f87e241adc64419bf12cab&spm_id_from333.788.videopod.episodes&p47 同步代码和异步代码回调函数地狱与解决方法回调函数地狱…...

编程日记 2025/5/13 23:06:01

Linux+Docer 容器化部署之 Shell 语法入门篇【Shell 循环类型】

文章目录一、Shell 循环类型二、Shell while 循环三、Shell for 循环四、Shell until 循环五、Shell select 循环六、总结一、Shell 循环类型循环是一个强大的编程工具，使您能够重复执行一组命令。在本教程中，您将学习以下类型的循环 Shell 程序&…...

编程日记 2025/5/16 4:57:41

【Redis】安装配置Redis超详细教程 / Linux版

Linux安装配置Redis超详细教程安装redis依赖安装redis启动redis停止redisredis.conf常见配置设置redis为后台启动修改redis监听地址设置工作目录修改密码监听的端口号数据库数量设置redis最大内存设置日志文件设置redis开机自动启动学习视频：黑马程序员Redis入门到…...

编程日记 2025/5/13 1:47:32

S4 HANA明确税金汇差科目(OBYY)

本文主要介绍在S4 HANA OP中明确税金汇差科目(OBYY)相关设置。具体请参照如下内容： 1. 明确税金汇差科目(OBYY) 以上配置点定义了在外币挂账时，当凭证抬头汇率和税金行项目汇率不一致时，造成的差异金额进入哪个科目。此类情况只发生在FB60/F…...

编程日记 2025/5/14 10:20:31

Nginx反向代理笔记250203

Nginx反向代理 Nginx 是一个高性能的 HTTP 服务器和反向代理服务器。反向代理是指客户端请求资源时，Nginx 作为中间层，将请求转发到后端服务器，并将后端服务器的响应返回给客户端。通过反向代理，可以实现负载均衡、缓存、SSL 终端…...

编程日记 2025/5/12 6:42:34

【ChatGPT：开启人工智能新纪元】

一、ChatGPT 是什么最近，ChatGPT 可是火得一塌糊涂，不管是在科技圈、媒体界，还是咱们普通人的日常聊天里，都能听到它的大名。好多人都在讨论，这 ChatGPT 到底是个啥 “神器”，能让大家这么着迷？今天咱就好好唠唠。 ChatGPT，全称是 Chat Generative Pre-trained Trans…...

编程日记 2025/5/14 1:19:39

OpenAI 实战进阶教程 - 第六节: OpenAI 与爬虫集成实现任务自动化

爬虫与 OpenAI 模型结合，不仅能高效地抓取并分析海量数据，还能通过 NLP 技术生成洞察、摘要，极大提高业务效率。以下是一些实际工作中具有较高价值的应用案例： 1. 电商价格监控与智能分析应用场景： 电商企业需要监控…...

编程日记 2025/5/14 9:28:40

49【服务器介绍】

服务器和你的电脑可以说是一模一样的，只不过用途不一样，叫法就不一样了物理服务器和云服务器的区别整台设备眼睛能够看得到的，我们一般称之为物理服务器。所以物理服务器是比较贵的，不是每一个开发者都能够消费得起的。 …...

编程日记 2025/5/12 10:25:56

docker pull Error response from daemon问题

里面填写里面解决方案就是挂代理。以虚拟机为例，将宿主机配置端口设置，https/http端口设为7899 配置虚拟机的http代理： vim /etc/systemd/system/docker.service.d/http-proxy.conf里面填写，wq保存 [Service] Environment…...

编程日记 2025/5/13 5:55:35

院校联合以项目驱动联合培养医工计算机AI人才路径探析

一、引言 1.1 研究背景与意义在科技飞速发展的当下，医疗人工智能作为一个极具潜力的新兴领域，正深刻地改变着传统医疗模式。从疾病的早期诊断、个性化治疗方案的制定，到药物研发的加速，人工智能技术的应用极大地提升了医疗服务…...

编程日记 2025/5/12 12:22:35

C++ Primer 标准库vector

欢迎阅读我的【CPrimer】专栏专栏简介：本专栏主要面向C初学者，解释C的一些基本概念和基础语言特性，涉及C标准库的用法，面向对象特性，泛型特性高级用法。通过使用标准库中定义的抽象设施，使你更加适应高级…...

编程日记 2025/5/12 16:09:36

Mac本地部署DeekSeek-R1下载太慢怎么办？

Ubuntu 24 本地安装DeekSeek-R1 在命令行先安装ollama curl -fsSL https://ollama.com/install.sh | sh 下载太慢，使用讯雷，mac版下载链接 https://ollama.com/download/Ollama-darwin.zip 进入网站 deepseek-r1:8b，看内存大小4G就8B模型 …...

编程日记 2025/5/12 8:48:19

kamailio-ACC_JSON模块详解【后端语言go】

要确认 ACC_JSON 模块是否已经成功将计费信息推送到消息队列（MQueue），以及如何从队列中取值，可以按照以下步骤进行操作： 1. 确认 ACC_JSON 已推送到队列 1.1 配置 ACC_JSON 确保 ACC_JSON 模块已正确配置并启用。以下…...

编程日记 2025/5/14 6:17:56

利用Python高效处理大规模词汇数据

在本篇博客中，我们将探讨如何使用Python及其强大的库来处理和分析大规模的词汇数据。我们将介绍如何从多个.pkl文件中读取数据，并应用一系列算法来筛选和扩展一个核心词汇列表。这个过程涉及到使用Pandas、Polars以及tqdm等库来实现高效的数据处理。引…...

编程日记 2025/5/15 17:49:45

k3s环境下安装hami提示如下错误： "failed to “StartContainer” for “kube-scheduler” with InvalidImageName: "Failed to apply default image tag “registry.cn-hangzhou.aliyuncs.com/google_containers/kube-scheduler:v1.31.2k3s1”: 没有Inva…...

编程日记 2025/5/14 5:30:47

2024美团春招硬件开发笔试真题及答案解析

目录一、选择题 1、在 Linux，有一个名为 file 的文件，内容如下所示： 2、在 Linux 中，关于虚拟内存相关的说法正确的是（） 3、AT89S52单片机中，在外部中断响应的期间，中断请求标志位查询占用了（）。 4、下列关于8051单片机的结构与功能，说法不正确的是（）？ 5、…...

编程日记 2025/5/14 3:56:44

HTML 字符实体

HTML 字符实体在HTML中，字符实体是一种特殊的表示方式，用于在文档中插入那些无法直接通过键盘输入的字符。字符实体在网页设计和文档编写中扮演着重要的角色，尤其是在处理特殊字符、符号和数学公式时。以下是关于HTML字符实体的详细解析。字符实体概述 HTML字符实体是一…...

编程日记 2025/5/11 3:34:08

FPGA|生成jic文件固化程序到flash

1、单击file-》convert programming files 2、flie type中选中jic文件，configuration decive里根据自己的硬件选择，单击flash loader选择右边的add device选项 3、选择自己的硬件，单击ok 4、选中sof选项，单机右侧的add file 5、选…...

编程日记 2025/5/15 8:20:24

Java | CompletableFuture详解

关注：CodingTechWork CompletableFuture 概述介绍 CompletableFuture是 Java 8 引入的一个非常强大的类，属于 java.util.concurrent 包。它是用于异步编程的一个工具，可以帮助我们更方便地处理并发任务。与传统的线程池或 Future 对比&…...

编程日记 2025/5/14 8:30:54

高阶开发基础——快速入门C++并发编程6——大作业：实现一个超级迷你的线程池

目录实现一个无返回的线程池完全代码实现 Reference 实现一个无返回的线程池实现一个简单的线程池非常简单，我们首先聊一聊线程池的定义： 线程池（Thread Pool） 是一种并发编程的设计模式，用于管理和复用多个线程…...

编程日记 2025/5/15 15:07:44

deep generative model stanford lecture note3 --- latent variable

1 Introduction 自回归模型随着gpt的出现取得很大的成功，还是有很多工程上的问题并不是很适合使用自回归模型： 1）自回归需要的算力太大，满足不了实时性要求：例如在自动驾驶的轨迹预测任务中，如果要用纯自回…...

编程日记 2025/5/11 12:17:15

【PDF提取局部内容改名】批量获取PDF局部文字内容改名基于QT和百度云api的完整实现方案

应用场景 1. 档案管理在企业或机构的档案管理中，常常会有大量的 PDF 格式的文件，如合同、报告、发票等。这些文件的原始文件名可能没有明确的标识，不利于查找和管理。通过批量获取 PDF 局部文字内容并改名，可以根据文件中的关键信息（如合同编号、报告标题等）为文件重新…...

编程日记 2025/5/14 6:11:14

吴恩达深度学习——卷积神经网络基础

本文来自https://www.bilibili.com/video/BV1FT4y1E74V，仅为本人学习所用。文章目录矩阵和张量边缘检测计算方式检测原理 Valid卷积和Same卷积卷积步长三维卷积单层卷积网络总结符号定义输入输出维度其他参数维度举例池化层示例输入层第一层卷积 - 池化第二层卷…...

编程日记 2025/5/12 5:24:24

MySQL锁详解

MySQL锁详解数据库的锁机制锁的分类行级锁与表级锁行级锁之共享锁与排他锁乐观锁与悲观锁悲观锁乐观锁 Innodb存储引擎的锁机制行级锁与表级锁的使用区分三种行锁的算法死锁的问题多版本并发控制MVCC 数据库的锁机制什么是锁？锁是一种保障数据的机制为何要用锁…...

编程日记 2025/5/15 15:24:26

快速提升网站收录：利用网站用户反馈机制

本文转自：百万收录网原文链接：https://www.baiwanshoulu.com/59.html 利用网站用户反馈机制是快速提升网站收录的有效策略之一。以下是一些具体的实施步骤和建议： 一、建立用户反馈机制多样化反馈渠道： 设立在线反馈表、邮件…...

编程日记 2025/5/12 17:22:22

初五，很棒

20元一瓶的水见过没？配料只有水和维C，养生佳品？除非我疯了。今晚和大姨爹等人探讨成家问题。没错，我变成最应该成家的人了。的确，从年龄上，发展阶段上，也是应该成家啦。难道我不知道嘛。人…...

编程日记 2025/5/13 10:55:41

Vue指令v-html

目录一、Vue中的v-html指令是什么？二、v-html指令与v-text指令的区别？ 一、Vue中的v-html指令是什么？ v-html指令的作用是：设置元素的innerHTML，内容中有html结构会被解析为标签。二、v-html指令与v-text指令的区别…...

编程日记 2025/5/10 4:50:00

ubuntu磁盘扩容

ubuntu磁盘扩容描述先在虚拟机设置里面扩容进入Ubuntu 配置使用命令行工具parted进行分区输出如下完成描述执行命令,查看 fs 类型是什么 lsblk -o NAME,FSTYPE,MOUNTPOINT将60G扩容到100G，其中有些操作我也不知道什么意思，反正就是成功了&#xff0…...

编程日记 2025/5/12 21:16:47

BFS（广度优先搜索）——搜索算法

BFS，也就是广度（宽度）优先搜索，二叉树的层序遍历就是一个BFS的过程。而前、中、后序遍历则是DFS（深度优先搜索）。从字面意思也很好理解，DFS就是一条路走到黑，BFS则是一层一层地展开。…...

编程日记 2025/5/12 17:31:51

SAP SD学习笔记27 - 请求计划(开票计划)之1 - 定期请求(定期开票)

上两章讲了贩卖契约（框架协议）的概要，以及贩卖契约中最为常用的基本契约 - 数量契约和金额契约。 SAP SD学习笔记26 - 贩卖契约(框架协议)的概要，基本契约 - 数量契约_sap 框架协议-CSDN博客 SAP SD学习笔记27 - 贩卖契约(框架…...

编程日记 2025/5/15 4:00:34

string例题

一、字符串最后一个单词长度题目解析：由题输入一段字符串或一句话找最后一个单词的长度，也就是找最后一个空格后的单词长度。1.既然有空格那用我们常规的cin就不行了，我们这里使用getline,2.读取空格既然是最后一个空格后的单词，…...

编程日记 2025/5/16 2:03:19

Revit二次开发自适应族添加放样融合

大多数博客给出的方案都是如何在有自适应族的情况下进行修改定位点或是将数据传入自适应族,如何直接在族文件中创建自适应模型并将点转换为自适应点,连接自适应点成为自适应路径这种方式没有文章介绍. 下面的代码中给出了如何在自适应族文件中创建参照点并转换为自适应点连接…...

编程日记 2025/5/12 18:28:51

浏览器模块化难题

CommonJS 的工作原理当使用 require(模块路径) 导入一个模块时，node会做以下两件事情（不考虑模块缓存）： 通过模块路径找到本机文件，并读取文件内容将文件中的代码放入到一个函数环境中执行，并将执行后 m…...

编程日记 2025/5/15 4:24:58

详细介绍：网站背景更换功能

目录 1. HTML 部分 2. JavaScript 部分 3. 完整流程 4. 总结 5. 适用场景本文将介绍如何通过文件上传实现网站背景图片的更换。通过使用 JavaScript 和 Axios，我们可以允许用户上传图片文件并将其作为网站的背景图片。上传的图片 URL 会保存在浏览器的 localSt…...

编程日记 2025/5/4 17:52:31