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 这个类。 此后基于二维

【多维分桶】力扣939,963-最小面积矩形

用坐标值对点做哈希,用哈希值 用中点和长度对点对(线段,圆)做哈希,用哈希值分桶 多层 treemap 对点对做多属性分桶 STL无序关联容器自定义哈希函数 939. 最小面积矩形题目描述给定在 xy 平面上的一组点,确定由这些点组成的矩形的最小面积,其中矩形的边平行于 x 轴和 y 轴。 如果没有任何矩形,就返回 0。 提示:12341 <= points.length

极角

摘要: 极角的原理和代码 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的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 各位好,本文我们来看一个使用分类讨论思想解决的问题。此前我们解决过另一个分类讨论的问题