计算几何

[](https://codeforces.com/blog/entry/86621?#comment-746863) 什么题是计算几何？cxy 第二定律告诉我们：若一道题出现坐标轴，且边不平行于坐标轴时，这道题才算是计算几何。所以说，[这种题](https://codeforces.com/gym/102992/problem/C) 就是典型的非计算几何题。 在此基础上，我剔除了一部分依赖于 Planarity 的题目（即一些在平面上有更优性质的问题），因为这些不能算作较为纯粹的计算几何。你可以在 [这个题单](https://www.luogu.com.cn/training/46711) 中看到这些题。 很多题的难度远远超出了对应算法的限制范围，你更应该把计算几何算法当成工具而非难度天花板。 选题的时候部分参考了 [StudyingFather 的题单](https://github.com/SFOI-Team/luogu-problem-list/blob/master/list.md#part-9-%E8%AE%A1%E7%AE%97%E5%87%A0%E4%BD%95) 和 [rui_er 的题单](https://www.luogu.com.cn/training/16408)。 每个 section 里面都是按难度排序的。 部分题链接前面没有题号，代表这些题洛谷没有。 ### 基础计算几何 指不需要用到任何更难的计算几何算法，只需要初中的知识。请注意这并不意味着这一 section 的题目比较简单。 - [Interested in Skiing](https://codeforces.com/gym/102992/problem/I)（[这个题现在洛谷也有了](https://www.luogu.com.cn/problem/P9630)） - [P1663 山](https://www.luogu.com.cn/problem/P1663) - [circle](https://ac.nowcoder.com/acm/contest/58833/C) ~~（夹带私货）~~ - [CF1381E Origami](https://www.luogu.com.cn/problem/CF1381E) ### 极角排序，坐标旋转 由于很多计算几何题仅限于此，所以单独列了个条目。 - [Laser Trap](https://codeforces.com/gym/104373/problem/C)（[这个题洛谷现在也有了](https://www.luogu.com.cn/problem/P9658)） - [P3699 [CQOI2017]小Q的草稿](https://www.luogu.com.cn/problem/P3699) - [P4605 [SDOI2018]物理实验](https://www.luogu.com.cn/problem/P4605) - [【UR #16】破坏蛋糕](https://uoj.ac/problem/242) - [AT_joisc2014_k 二人の星座](https://www.luogu.com.cn/problem/AT_joisc2014_k) ### Someone's Trick 这个 trick 貌似并没有一个名字，但是很普遍，所以就单独列了个条目。 - [P2924 [USACO08DEC]Largest Fence G](https://www.luogu.com.cn/problem/P2924) - [CF852H Bob and stages](https://www.luogu.com.cn/problem/CF852H) - [CF1326G Spiderweb Trees](https://www.luogu.com.cn/problem/CF1326G) - [P5403 [CTS2019] 田野](https://www.luogu.com.cn/problem/P5403) ### 凸包 这里只收录计算几何相关的凸包，凸优化并不在考虑范围内。 - [CF1017E The Supersonic Rocket](https://www.luogu.com.cn/problem/CF1017E) - [P9845 Paimon Polygon](https://www.luogu.com.cn/problem/P9845) - [Master of Both V](https://qoj.ac/problem/8241) - [Master of Polygon](https://qoj.ac/problem/6403) ### 凸包的闵可夫斯基和 之前以为是没必要单独列出来的，现在感觉还是有的（ - [Amazing spacecraft](https://acm.hdu.edu.cn/showproblem.php?pid=7278) - [P4557 [JSOI2018] 战争](https://www.luogu.com.cn/problem/P4557) - [魔法阵](https://www.matiji.net/exam/brushquestion/23/4347/179CE77A7B772D15A8C00DD8198AAC74) ### 半平面交 欢迎来到 CNOI 计算几何最高城。 一部分直接半平面交的题目，由于套路过于雷同，就没有选进来。 - [Jungle Outpost](https://codeforces.com/gym/101309/problem/J) - [P4250 [SCOI2015]小凸想跑步](https://www.luogu.com.cn/problem/P4250) - [P3297 [SDOI2013] 逃考](https://www.luogu.com.cn/problem/P3297) - [P5328 [ZJOI2019] 浙江省选](https://www.luogu.com.cn/problem/P5328) - [Epidemic Escape](https://qoj.ac/problem/5570) - [【ULR #1】卫星基站建设](https://uoj.ac/problem/579) ### 反演 别急，让我研究。 - [Drawing Circles is Fun](https://codeforces.com/contest/372/problem/E) ### 半平面数据结构 从这里开始往下大概就是科技的范畴。 这里主要指的是分块。 - [【UNR #4】己酸集合](https://uoj.ac/problem/553) - [【UR #16】破坏导蛋](https://uoj.ac/problem/243) - [P8261 [CTS2022] 袜子](https://www.luogu.com.cn/problem/P8261) ### 梯形剖分 / 三角剖分 一个不是很广为人知的事实是，得到了一个多边形的梯形剖分就可以得到一个多边形的三角剖分。 学术界有严格/期望 $O(n)$ 的梯形剖分算法，但对于一般的题目，$O(n\log n)$ 的扫描线就可以解决。 - [CF223D Spider](https://www.luogu.com.cn/problem/CF223D) - [P3316 [SDOI2014] 里面还是外面](https://www.luogu.com.cn/problem/P3316) - [Map 2](https://qoj.ac/problem/8054) - [LaLa and Magic Circle (LaLa Version)](https://qoj.ac/problem/6375) ### 平面图相关 大概有，平面图转对偶图，平面图分治之类的。后者可以去看 127 论文。 - [P3249 [HNOI2016] 矿区](https://www.luogu.com.cn/problem/P3249) - [P4073 [WC2013] 平面图](https://www.luogu.com.cn/problem/P4073) ### Delaunay 三角剖分 不会，先鸽着。 ### 三维计算几何 我一点都不会这个啊？ - [P4508 [CTSC2011] 杀菌计划](https://www.luogu.com.cn/problem/P4508) - [P4502 [ZJOI2018] 保镖](https://www.luogu.com.cn/problem/P4502) ### MO 相关 这部分的题大量依赖于 MO 方面的推导，比较偏，其实也没太多意思。 - [CF603D Ruminations on Ruminants](https://www.luogu.com.cn/problem/CF603D) - [CF1726H Mainak and the Bleeding Polygon](https://www.luogu.com.cn/problem/CF1726H)