计算几何专题练习记录

部分题目参考来源：1 2 3 《算法竞赛入门经典——训练指南》

计算几何专题练习记录（二）：link

基础知识应用

• poj 2318 TOYS: 判断点在直线的左右。$\star$
• poj 2398 Toy Storage: 同上。$\star$
• poj 1556 The Doors: 判断线段相交，建图跑最短路。$\star\star$
• poj 1696 Space Ant: 从最低点开始尽可能左转少的角度，卷包裹。$\star\star$
• poj 3304 Segments: 转化问题为找一条直线与所有线段相交，又易知平移旋转该直线可使其与两个线段端点重合，故枚举即可。$\star\star\star$
• poj 1127 Jack Straws: 线段相交，并查集。$\star$
• poj 1654 Area: 多边形面积。$\star$
• poj 1408 Fishnet: 四边形面积。$\star$
• poj 2954 Triangle: Pick 定理，gcd 计算边上的点数。$\star$
• poj 2031 Building a Space Station: 球体相交，最小生成树。$\star$
• poj 1584 A Round Peg in a Ground Hole: 判断圆是否在凸多边形内部时，首先看圆心是否在多边形内，然后看距离与半径大小。$\star$
• poj 3334 Connected Gheeves: 二分答案，多边形面积。$\star\star$
• poj 1819 Disks: 计算相切时圆心，不要忘了处理开头与结尾。$\star\star$
• poj 2826 An Easy Problem?!: 情况容易漏掉，另外还有一个坑：输出时可能输出 -0.00，应加上 eps 后再输出。$\star\star\star$
• poj 2074 Line of Sight: 视线遮挡问题。$\star\star$
• poj 1039 Pipe: 容易发现一定存在过一个上端点、过一个下端点的最优光路，于是枚举端点，依次判断相交即可，注意端点相交的处理。$\star\star$
• poj 1418 Viva Confetti: 每一个可见部分都由几段小圆弧构成，可以先求出所有小圆弧，将其中点向内向外扰动一点点得到两点，标记包含这两点的最顶端的圆盘为可见。$\star\star\star\star$
• UVA 11817 Tunnelling the Earth: 球面距离。$\star$
• UVA 10969 Sweet Dream: 和 poj1418 类似，找出所有小圆弧，用其中点判断该段小圆弧是否被覆盖。$\star\star\star$
• UVA 11178 Morley’s Theorem: 角度计算、向量旋转、直线相交。$\star$
• UVA 1342 The Nice Euler Circuits: 欧拉定理，线段相交。$\star\star$
• UVA 11796 Dog Distance: 模拟，把同时运动的距离最值转化成点到线段距离最值（绝对速度转化为相对速度）$\star\star$
• UVA 11177 Fighting against a Polygonal Monster: 二分答案，多边形与圆相交的面积。$\star\star\star$
• UVA 1340 Find The Border: 卷包裹，从最左下端开始沿着线段走，走到一个交点后尽可能地右转，继续走。$\star\star\star$
• UVA 12296 Pieces and Discs: 切割多边形；判断多边形与圆的位置关系：圆心在多边形内或圆心到多边形边（是一系列线段）的距离小于圆的半径）$\star\star\star$
• CF 1254C Point Ordering: 交互题。首先用 $n-2$ 次提问确定 $3$ 至 $n$ 这些点在 $1,2$ 两点连线的左右，对于左边的那些点（右边同理），用第一种提问得到它们到 $1,2$ 连线的距离，找到最远的点 $mark$，判断其他点是在 $1,mark$ 之间还是 $mark,2$ 之间，分别按距离排序后就形成了逆时针方向。$\star\star\star\star$
• CF 961D Pair Of Lines: 找三个不共线的点，两两配对连线作为一条直线，判断其余点是否在这条线上或构成另一条线。$\star\star$
• CF 1059D Nature Reserve: 二分答案，check：判断一个半径为 $r$ 的圆能否覆盖所有点，即判断以每个点为圆心、以 $r$ 为半径构造的圆是否有公共交点，又圆心在 $y=r$ 上，只需判断构造的圆与 $y=r$ 交成的线段是否有公共交点即可。小心卡精度，用 long double 并且二分150次就退出。$\star\star\star\star$

初中平几

• UVA 11437 Triangle Fun: 梅涅劳斯定理。$\star$
• UVA 11800 Determine the Shape: 判断四边形形状。$\star$
• UVA 11646 Athletics Track: 平几。$\star$
• UVA 11524 InCircle: 内切圆。$\star$
• UVA 11731 Ex-Circles: 旁切圆。$\star\star$
• UVA 10566 Crossed Ladders: 相似三角形，二分答案。$\star$
• UVA 11186 Circum Triangle: 把三角形面积拆成和圆心连线后的三个三角形面积之和/差，枚举边，数多少取正多少取负。$\star\star\star$
• UVA 1447 Malfatti Circles: 内切圆，推不出公式可以二分。$\star\star\star$
• UVA 12165 Triangle Hazard: 梅涅劳斯定理。$\star\star$
• UVA 1473 Dome of Circus: 转化为平面坐标系，三分。$\star\star$

反演变换

• hdu 4773 Problems of Apollonius: 视要求经过的点为反演中心，任取反演半径，则根据反演的性质，所求圆反演后是一条直线，且与给定两圆的反演圆相切，即反演直线是两反演圆的公切线。于是求得公切线之后再反演回去即可。$\star\star\star\star$
• hdu 6158 The Designer: 选取两大圆的切点为反演中心，任取反演半径，则两大圆反演为两直线，所有小圆的反演圆都是夹在这两条直线之间的半径相同的圆，根据反演圆的信息倒推小圆半径即可。当答案小到不影响精度时就 break 掉。$\star\star\star$

平面最近点对

• luogu P1429: 模板
• poj 3714 Raid: 对模板略加修改即可。$\star$

凸包

• luogu P2742: 模板
• poj 1873 The Fortified Forest: 二进制枚举，求凸包。$\star\star\star$
• poj 1228 Grandpa’s Estate: 判断凸包是否存在仅有两个点的边。$\star\star$
• poj 3348 Cows: 求凸包面积。$\star$
• poj 1113 Wall: 凸包周长。$\star$
• [SHOI2012]信用卡凸包: 凸包周长加一个圆周长。$\star$
• UVA 10652 Board Wrapping: 求凸包面积。$\star$
• UVA 109 SCUD Busters: 求凸包及面积，判断点在多边形内。$\star$
• UVA 11168 Airport: 凸包，总距离需要转换为解析几何的思路方可 $O(1)$ 计算。$\star\star$
• UVA 10256 The Great Divide: 判断两凸包是否有公共部分——看点在不在对方凸包内、看凸包线段是否相交。$\star\star\star$
• CF 1142C U2: 很妙的一道题！抛物线函数式改写成：$y-x^2=bx+c$，我们发现如果把所有点 $(x,y)$ 改成 $(x,y-x^2)$，那么抛物线就变成了直线，一个点在原抛物线内等价于改动后的点在直线上方，所以求出上凸包的边数即可。$\star\star\star\star$

旋转卡壳

• luogu P1452: 求凸包直径。$\star$
• poj 2187 Beauty Contest: 求凸包直径。$\star$
• UVA 1453 Squares: 求凸包直径，输入可能重复，需要去重。$\star\star$
• poj 3608 Bridge Across Islands: 求两凸包之间的最短距离。$\star\star\star$
• [HNOI2007]最小矩形覆盖: 求覆盖所有点的最小面积矩形，先求出凸包，这个矩形的一条边一定与凸包的一条边共线，于是旋转卡壳枚举矩形一条边，找到对踵点作为对边上的点，然后向左向右找到左右边界。找左右边界时找投影长度最长的点，容易发现投影长度函数是单峰的，所以可以三分法求得（然而与暴力找时间开销几近相同）$\star\star\star$
• UVA 12307 Smallest Enclosing Rectangle: 求覆盖所有点的最小面积矩形和最小周长矩形：最小周长矩形也是一定有一条边与凸包一条边共线，在 HNOI2007 的最小面积矩形的基础上稍加改动即可。$\star\star\star$

半平面交

• poj 3335 Rotating Scoreboard: 模板，判断多边形是否有核。

• poj 3130 How I Mathematician Wonder What You Are!: 模板，同上。

• poj 1474 Video Surveillance: 模板，同上。

• poj 1279 Art Gallery: 模版，求多边形核的面积。

• [CQOI2006]凸多边形: 模版，同上。

• poj 2451 Uyuw’s Concert: 同上。

• poj 3525 Most Distant Point from the Sea: 求凸多边形最大内切圆，二分答案，判断半平面交是否为空。$\star\star$

• poj 3384 Feng Shui: 把问题转化为求将每条边向内平移 $r$ 长度后形成的凸多边形直径，该凸多边形用半平面交来生成。$\star\star\star$

• poj 2540 Hotter Colder: 把条件转化为半平面，注意方向。$\star\star\star$

• poj 1755 Triathlon: 设第一段长 $a$，第二段长 $b$，第三段长 $1-a-b$，列出 $i$ 快于 $j$ 的表达式，得到线性规划区域，半平面交判断是否有解。此题卡精度，需设置 eps=1e-16。$\star\star\star$

• [JSOI2004]平衡点: 初始平面是整个平面，取平面的中心，计算合力，则平衡点一定在合力指向的那个半平面上，于是不断二分、不断用半平面切割平面，直到剩余平面够小了则输出。$\star\star\star\star$

• UVA 1475 Jungle Outpost: 假设已知敌人炸了 $k$ 座瞭望台，我们可以通过数归证明敌人的最优策略是炸掉连续的 $k$ 座瞭望台，此时，对应不同连续 $k$ 座被炸的瞭望台，保留部分是不同的半平面，它们交集非空，则总部设在其交集中便总能被保护。于是二分答案，判断半平面交是否为空。$\star\star\star$

• [SCOI2015]小凸想跑步: 列式表示 $\Delta p01<\Delta pab$：$(x-x_0,y-y_0)\times(x-x_1,y-y_1)<(x-x_a,y-y_a)\times(x-x_b,y-y_b)$，整理得：$(y_0-y_1+y_b-y_a)x+(x_1-x_0+x_a-x_b)y<x_1y_0-x_0y_1+x_ay_b-x_by_a$，为一个半平面，计算半平面面积。

  备注：$ax+by+c<0$ 表示半平面时，方向向量为 $(-b, a)$. $\star\star\star$

扫描线

• poj 1151 Atlantis: 模板，数据不大，可暴力。
• luogu P5490: 模板
• poj 3832 Posters: 注意不能添加空矩形区域，否则会 RE.
• poj 1177 Picture: 求图形周长，线段树需要多维护一个区间覆盖段数的信息，扫描线每扫到一个高度，竖直方向上周长加上两倍段数乘以高度，水平方向上周长加上当前覆盖长度与前一个覆盖长度的差的绝对值。$\star\star\star$
• luogu P1502 窗口的星星: 每一颗星星右上方划出一块 $W\times H$ 的矩形区域，则窗户右上角落在该区域内时该星星可见。于是可以扫描线解之，线段树维护区间加、区间求最大值操作。$\star\star\star$
• poj 2932 Coneology: 由于两圆不可能有交点，所以一个圆覆盖另一个等价于另一个圆的圆心在这个圆内，然后从下往上扫描，每扫到一个圆的下界时判断这个圆有没有被已经扫过的圆覆盖，如果没有，则它一定是不被任何圆覆盖的；判断时，只需要判断当前圆左边横坐标方向最近的和右边横坐标方向最近的圆是否覆盖它即可，因为如果这两个圆都不覆盖的话，其他圆更不可能覆盖。于是乎，我们可以用一个可查询前驱或后继的数据结构维护不被任何圆覆盖的圆这个集合——平衡树、STL 的 set、值域线段树都可以。$\star\star\star\star$
• hdu 1255 覆盖的面积: 由于没有 pushdown 操作，需要深入理解 cnt 标记——cnt == 0 表示区间信息完全未知，更新信息从子节点直接更新；cnt == 1 表示区间被覆盖至少 $1$ 次（有可能更多次），更新信息时，被覆盖 $2$ 次的长度等于左右子节点被覆盖 $1$ 次的长度和（因为已知本身被覆盖至少 $1$ 次，而这 $1$ 次是不会下放到子节点的）；cnt >= 2 表示区间被覆盖至少 $2$ 次（有可能更多次），被覆盖 $2$ 次的长度等于区间长度。$\star\star\star$
• World Finals 2008 The Sky is the Limit: 记录山顶、山脚和交点的横坐标，扫描线从左往右扫之，在每个区间内枚举寻找最高的线段即可。$\star\star$

三维凸包

• luogu P4724: 模板
• hdu 3662 3D Convex Hull: 求三维凸包的面数。$\star$
• hdu 4266 The Worm in the Apple: 求凸包内的点到凸包表面的最小距离。$\star$
• hdu 4273 Rescue: 求凸包重心到凸包表面最小距离。多面体重心求法：任取一点，用该点与多面体的面形成的三角锥分割多面体，三角锥的重心即其各顶点坐标的平均值，多面体的重心即各三角锥的重心坐标按照其质量（体积）加权的平均值。$\star\star$

计算几何背景

以计算几何为背景，考察构造思维或其他算法。

• UVA 1318 Monster Trap: （计算几何+图论）容易知道，若怪物能逃离，则存在擦着一系列线段端点的逃离路径，也就是说，能两两连接不被隔断的线段端点之间建一条边，则跑一遍 dfs 或者 bfs 即可。问题在于，若有两个线段在转角处端点重合，这么建边会使得怪物可以在转角处穿墙而过，解决方案是把每一个线段都向两端延长一点点；再注意要特殊处理具有公共端点的线段共线的情况。$\star\star\star\star$
• CF 1270E Divide Points: （计算几何+构造）从距离的奇偶性入手。把点分成四类：$(odd,odd),(odd,even),(even,odd),(even,even)$，如果只存在其中一类点，就将坐标不断除以2后重新分类；如果存在两类点，则其中一类作为 $A$ 集合，另一类作为 $B$ 集合，它们之间的距离有奇偶之分或是否整除 $4$ 之分；如果存在三类以上的点，则横纵坐标和为奇数作为 $A$ 集合，和为偶数作为 $B$ 集合，它们之间的距离有奇偶之分。$\star\star\star\star$