计算几何题集 #

二维基础 #

NC [2021江苏省赛热身赛]Magic Rabbit #

给定三种无限量包含两种溶质的溶液分别浓度分别为 $a_i, b_i(i = 1, 2, 3)$，给定 $q$ 次询问，每次给定 $x, y$ 问能否配置出这两个对应浓度的溶液 $1 \leq q \leq 10^5$

• 如果我们按两个参数建立坐标系，可以证明，能配置出来的浓度范围应该是在这三个点构成的三角形内(包含退化三角形)，于是转化为点是否在凸多边形内部
• 这里给出是因为可以推广到 $n$ 中溶液，或者三种溶质，转化为求这些点凸包即可，然后判定点是否在凸包内

NC [2020Hdu]三角碰撞(Triangle Collision) #

坐标系中有一个对称放置的正三角形，边长为 $L$，再给定一个三角形内部的点，质量无穷小，坐标 $(x, y)$，具有速度向量 $(dx, dy)$，这个点碰到正三角形边上会完全弹性碰撞，初始时间为 $0$，计算恰好碰撞第 $k$ 次时所用的时间，保证不会恰好与三角形顶点碰撞 $T \leq 10^4$ 组测试，$1 \leq L, x, y, dx, dy \leq 10^4, 1 \leq k \leq 10^6$

• 碰撞问题常常使用对称构成一个无穷大网格图，转化为直线与网格图的第 $k$ 个交点的问题，可以使用二分答案，时间复杂度 $O(Tlog\frac{V}{\varepsilon})$

[2017WF]Airport Construction #

给定一个 $n$ 边形，求一条最长的线段使得线段完全在这个 $n$ 边形内部 $1 \leq n \leq 200, |x|, |y| \leq 10^6$

• 首先不加证明的给出无论凹凸，这条最长的线段总是至少通过两个顶点(注意在凹多边形下线段端点不一定是顶点)
• 于是我们枚举这两个顶点获得直线，接着遍历多边形获取所有交点并排好序，将直线分割成若干线段，于是分别判断每一段是否在多边形内，这里判断可以选择判断中点是否在多边形内
• 如果我们直接选择判断，总时间复杂度是 $O(n^4)$，但由于交点个数大概率无法取到接近上界 $n$ 所以卡卡常是完全能过的。但事实上由于待判断的若干线段共线，所以回转数的计算可以从上一个位置转移，可以做到 $O(n^3logn)$ 的复杂度，实现就比较困难了

类似写法的简单题：LG P3738 [HAOI2014] 穿越封锁线

NC Cross on a Plane #

定义十字架图形是由一个正方形的四条边无线延长并去掉初始正方形四边部分的图形，十字架的大小定义为正方形边长长度。给定一个 $n$ 元点集，计算最小十字架使得所有点在十字架内部 $1 \leq n \leq 50, |x|, |y| \leq 10^4$

• 我一开始的想法认为最终解是这样两种情况，一是其中一对平行直线中一个通过至少两个点，一个通过至少一个点，另一种是两个各通过一个点，但该组平行线与这两点连线垂直

上面的结论在仅两条平行直线时应该是对的，但在存在另一组平行线时不对，结论应该是更弱的

• 最优解至少存在一组平行直线，各过至少一个点(这个条件就正确了)，我们二分答案，接着遍历两组点于是就能确定一对平行直线，接着考察在平行线范围外部的点的投影判断即可，时间复杂度 $O(n^3logn)$
• 在具体细节中我们又有两个问题

1. 首先在给定平行线距离和两个点怎么确定两条直线，我们可以使用三角函数对向量旋转做到这一点
2. 当二分的平行线距离大于两点距离时应该怎么办？我们认为在这种情况下就取定平行线距离等于两点距离的平行线(即该组平行线与这两点连线垂直)，为什么是正确的？读者自证

极角排序 #

直线旋转 #

[2016WF]Oil #

给定 $n$ 条平行于 $x$ 轴的线段，线段两个端点分别为 $(x_0, y), (x_1, y)$，我们认为如果直线与线段相交(包含端点)，则获得线段长度作为权值，求一条不平行于 $x$ 的直线能获得的最大权值 $1 \leq n \leq 2 \times 10^3, |x_0|, |x_1| \leq 10^6, 1 \leq y \leq 10^6$

• 首先我们需要注意到在 $n > 1$ 且 $\exist y_1, y_2, 有 y_1 \neq y_2$ 时能取到最大值的直线中一定存在一条至少通过两个端点，由于在这个情况下这类直线至少通过两条线段，可以对该直线进行调整使得通过某两个端点(好像也并不严谨)
• 于是最朴素的想法是枚举两个端点确定直线，这样时间复杂度是 $O(n^3)$ 不可接受，我们尝试转变思路
• 我们先确定一个端点，接下来直线形成旋转直线系，我们可以对其余剩余节点关于枚举点做极角排序
• 但依然有一些细节问题，我们需要对纵坐标大于枚举点和小于枚举点分类处理，使得我们只考虑上或下半平面，转化为射线问题，由于存在共线的点我们需要使用map对点关于极角排序维护，时间复杂度 $O(n^2logn)$

NC [ICPC2004上海]Amphiphilic Carbon Molecules #

给定平面上 $n$ 个点的坐标，每个点有黑色或白色两种颜色，现需要划定一条直线，使得直线一侧的黑色点个数和另一侧白色点个数之和最大，直线上的点无论黑白都计算在其中，求最大个数 $1 \leq n \leq 10^3, |x|, |y| \leq 10^4$

• 类似上一个题，我们枚举每一个点，接着将其余点关于枚举点极角排序，我们可以使用下半平面翻转的技巧(但注意颜色也翻转)，顺序遍历维护左右半平面的白色黑色点的个数，更新答案，最终时间复杂度 $O(n^2logn)$

平面旋转 #

NC [2020WF]Ley Lines #

给定平面上 $n$ 个点的坐标，保证没有三点共线，问使用距离为 $t$ 的一组平行线能最多使得多少个点在平行线内部 $3 \leq n \leq 3 \times 10^3, 0 \leq t, |x|, |y| \leq 10^9$

• 一个类似之前十字架的题，但点数更多
• 类似的我们不加证明的给出取到最优解的情况中存在一条直线至少通过两个点，一个朴素的想法就是枚举这两个点，时间复杂度 $O(n^3)$ 是不可接受的
• 我们考察平面旋转即坐标系旋转过程中，所有点横坐标的相对变化，当y轴方向恰好平行某两个点连线时，恰好是这两个点相对位置变化的时刻，且在这个时候我们可以观察以这两点连线为平行线时的最大个数(使用二分)
• 也就是说我们可以对 $O(n^2)$ 组连线方向做极角排序，维护好每一个角度下所有点横坐标的相对大小，接着在交换时二分更新答案，最终时间复杂度 $O(n^2logn)$

NC [2021ICPC网络赛第二场]Nearest Point #

给定平面上 $n$ 个点的坐标，我们认为两个点 $y$ 是 $x$ 最近点是指所有点在x轴上投影下其余所有点到 $x$ 的距离中 $y$ 到 $x$ 的距离最小，从而每一个点都会有一个最近点，现在我们对所有点随机的绕原点一个角度，希望计算对任意 $x, y$，$y$ 是 $x$ 最近点的概率，打印最后的概率矩阵 $2 \leq n \leq 50, |x|, |y| \leq 10^3$

一些计数问题 #

NC [POI2008]Tro #

给定平面上 $n$ 个点的坐标，求这些点形成的所有三角形的面积之和 $3 \leq n \leq 3 \times 10^3, 0 \leq x, y \leq 10^4$

• 首先我们想到叉乘关于向量加法的结合率，但是我们注意到我们要求的面积时带上绝对值的，这需要我们保证合并的点在同一个半平面，去重也是需要注意的问题
• 给出一种一个便于实现的方法，解决这个问题可以首先将这些点按横纵坐标排序，对于每个点我们仅考虑后缀的点形成的三角形，且这些点天然在同一个半平面，接着关于枚举点极角排序，以次枚举一条边，使用向量的后缀和累加面积，时间复杂度 $O(n^2logn)$

NC [2016Hdu]How Many Triangles #

给定平面上 $n$ 个点的坐标，求这些点形成的所有三角形中锐角三角形的个数 $3 \leq n \leq 2 \times 10^3, 0 \leq x, y \leq 10^9$

• 暴力枚举三个点是 $O(n^3)$ 不接受
• 首先的核心思路是锐角三角形不好计数，但直角三角形和钝角三角形是容易的(注意在这个题中共线可以当成平角)，所以我们转去计算出非锐角三角形个数
• 枚举一个点作为大于等于90度夹角的顶点，其余点关于枚举点进行极角排序，我们可以使用双指针维护大于等于90度夹角的区间，实现稍微不太方便，时间复杂度 $O(n^2logn)$

NC [JOISC 2014Day4]两个人的星座 #

给定平面上的若干个点，每个点有红黄蓝中一种颜色，保证没有三点共线和重合点，定义好三角形是满足三个顶点恰好颜色不同的三角形，问有多少对相离的好三角形 $6 \leq n \leq 3 \times 10^3, |x|, |y| \leq 10^5$

• 我们可以转去思考一个更简单的问题，对于一个三种数字的数列，选择两个相离的三元子序列包含三种数字的方案数如何计算，我们自然能想到枚举断点
• 关于凸多边形相离，我们有一个性质，两个相离凸多边形有四条公切线，两条外公切线，两条内公切线，且切点必然通过顶点
• 利用上述性质，我们希望遍历每一条过两点的直线作为内公切线，这两点恰好就是两个三角形其中一个点，接着只需要保证计数的三角形不在一个半平面即可，所以我们需要维护好平面两侧三种点的个数，这就启发我们枚举一个点接着关于这个点极角排序(同样对称做更方便一些)，最终复杂度 $O(n^2logn)$

凸包 #

旋转卡壳 #

凸包上的二分 #

下面三个题是同一个题目，难度越来越高

NC [2016-2017ICPC PNRC(div1)]Enclosure #

给定 $n$ 个点，前 $k$ 个点是我们获得的，现询问从剩下 $n - k$ 个点中选择恰好一个的情况下，这 $k + 1$ 个点形成的凸包的最大面积 $3 \leq k < n \leq 10^5, |x_i|, |y_i| \leq 10^9$

NC [2021CCPC网络赛第一场]Start Dash ! ! #

NC [2021CCPC广州]Dynamic Convex Hull #

闵可夫斯基和 #

NC [JSOI2018]战争 #

给定两个分别有 $n, m$ 条边的凸多边形，给定 $q$ 次询问，每次给定一个向量 $(dx_i, dy_i)$，查询第二个凸多边形向这个向量方向平移后是否相交(出现边界相遇) $3 \leq n, m \leq 10^5, 1 \leq q \leq 10^5, |x_i|, |y_i|, |dx_i|, |dy_i| \leq 10^8$

• 判断多边形相交可以使用闵可夫斯基和，这里实际可以不平移转而考虑该向量对于的点是否位于闵可夫斯基和内

NC Mogohu-Rea Idol #

给定三个 $n_i$ 个顶点的凸多边形，给定 $q$ 次询问，每次询问给定一个点 $(x_i, y_i)$ 询问是否存在分别位于三个凸多边形内部(包括边上)的三个点，使得带查询点恰好是重心 $3 \leq n_i \leq 5 \times 10^4, 1 \leq q \leq 10^5$

• 根据重心的坐标公式，这个题目很好转化到判断点是否位于三个凸包的闵可夫斯基和内

动态凸包 #

半平面交 #

扫描线 #

圆有关问题 #

基本几何元素 #

NC 2D Geometry 110 in 1! #

比较复杂的模拟，给定各种元素求圆心半径 可以用来测板子：外接圆内切圆直线交点和切线

NC [2021杭电多校8] Square Card #

给定二维平面上两个圆的圆心 $(x_i, y_i)$ 和半径 $r_i$，现一个边长为 $a$ 的正方形随机的放置再平面上，问它完全位于第一个圆中的情况下，完全位于两个圆中的概率 $-10^3 \leq x_i, y_i \leq 10^3, 0 < r_i, a \leq 10^3$

• 正方形完全位于圆中，我们考察正方形中心的范围，事实上这个圆心的范围是一个更小的同心圆，对于两个圆都是这样，所以最后由几何概型转化为两个新圆的面积交比上第一个圆的面积

NC [2014ICPC广州]Signal Interference #

给定二维平面上一个 $n$ 顶点多边形 $(x_i, y_i)$ 足 $k|P - A| \geq |P - B|$ 的所有点形成的轨迹与多边形的交面积 $1 \leq n \leq 500, |x|, |y| \leq 10^3, 0.2 \leq k < 0.8$

• 其实就是阿波罗尼斯圆与多边形交面积

圆的反演 #

最小圆覆盖 #