Tag: 计算几何

力扣LCP37-最小矩形面积

摘要: LCP37,计算几何问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 今天我们来看一个比较难的计算几何题,力扣 LCP37,本题是2021力扣杯春季赛团队赛第5题。算法要点如下: 两条直

射线旋转扫描线算法(Angular-Sweep)

摘要: 扫描线算法:射线旋转扫描 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,扫描线算法是计算几何中非常重要的一个算法,并且可以用于解决很多区间类的问题。扫描线算法中的扫描方式分为直线平移

一点绕另一点旋转

摘要: 一点绕另一点旋转的原理和代码 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 点(向量) $\vec{P}$ 绕 O 旋转 $\theta$点 $\vec{P}$ 绕原点 O 旋转后的点为 $

半平面交

摘要: 本文介绍计算几何中半平面交算法 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,在文章 向量的实现 中,我们实现了一个二维向量的代码模板,主要是 Vector2 这个类。 此后基于二维

【多维分桶】最小面积矩形

摘要: 分桶算法的在计算几何的应用 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在计算几何中,分桶是一种常用的算法,例如 N 个点中最多有多少点共线,本文我们继续看一个分桶处理的问题:最小面积矩形

极角

摘要: 极角的原理和代码 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文首先介绍一下极角的知识点,和代码模板,之后解决力扣的一道相关题目 1610。 向量的极角以原点 O 为极点,从 x 轴正方

摘要: 本文介绍计算几何中与点相关的基本问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,在文章 向量的实现 中,我们实现了一个二维向量的代码模板,主要是 Vector2 这个类。 本文我

凸包的直径,旋转卡尺算法

摘要: 本文介绍计算几何中求凸包的直径的算法:旋转卡尺 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,在文章 向量的实现 中,我们实现了一个二维向量的代码模板,主要是 Vector2 这个类

扫描线算法(Line-Sweep)

摘要: 扫描线算法:直线平移扫描 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,本文我们介绍一个计算几何中非常重要的算法:扫描线算法。除了计算几何之外,扫描线算法还可以解决很多区间的问题,力

多边形

摘要: 本文介绍计算几何中与多边形相关的基本问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,在文章 向量的实现 中,我们实现了一个二维向量的代码模板,主要是 Vector2 这个类。 此

直线和线段

摘要: 本文介绍计算几何中与直线和线段相关的基本问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,在文章 向量的实现 中,我们实现了一个二维向量的代码模板,主要是 Vector2 这个类。

【模板】二维向量的实现

摘要: 本文介绍一个向量的代码模板,解决几何问题是会频繁使用 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,本文介绍一个向量的代码模板,解决几何问题是会频繁使用,在文章 几何题汇总 中,我们

凸包

摘要: 本文介绍计算几何中关于凸包的基本问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,在文章 向量的实现 中,我们实现了一个二维向量的代码模板,主要是 Vector2 这个类。 此后基

几何题汇总

摘要: 本文总结了 leetcode 上的计算几何相关的题目 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 文总结了力扣上 2000 题以内的关于计算几何的 15 道题。将场景相同的放到了一起,场景

曼哈顿距离

摘要: 曼哈顿距离相关的几道题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在上一篇文章 通过分类讨论拆目标函数中的绝对值 中,我们看了一个比较简单的目标函数带绝对值的优化问题,目标函数的形式是下

【分类讨论】力扣335-路径交叉

摘要: 本文详细拆解 力扣335-路径交叉,核心是分类讨论的思想 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,本文我们来看一个使用分类讨论思想解决的问题。此前我们解决过另一个分类讨论的问题

【多维分桶】N 个点中最多有多少点共线

摘要: 分桶算法的经典题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 分桶法 中,我们系统梳理了力扣上关于分桶法的题目。 本文我们解决一个多维分桶的经典计算几何问题:N 个点中最多有多少点