几何题汇总

摘要: 本文总结了 leetcode 上的计算几何相关的题目

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

文总结了力扣上 2000 题以内的关于计算几何的 15 道题。将场景相同的放到了一起，场景上主要涉及点、直线、极角、凸包、多边形。算法上主要涉及多维分桶、扫面线算法。这两个算法相对来说小众一些，但是在 leetcode 也是有一些题的，在文章 分桶法 和 区间问题汇总 中分别做过汇总，最好都要掌握。刷完这份题目列表，力扣上的计算几何的问题可以说刷爆了。

直线和线段

• 面试题 16.03. 交点
• 面试题 16.13. 平分正方形

点

• 1232. 缀点成线
• 1401. 圆和矩形是否有重叠

极角

• 1610. 可见点的最大数目

多边形

• 469. 凸多边形
• 593. 有效的正方形
• 836. 矩形重叠

多维分桶

• 149. 直线上最多的点数
• 面试题 16.14. 最佳直线
• 939. 最小面积矩形
• 963. 最小面积矩形 II

凸包

• 587. 安装栅栏

---

扫描线算法

线扫描

• 223. 矩形面积

角扫描

• 1453. 圆形靶内的最大飞镖数量

---