2022010910017-谢卿云-计算几何专题报告

Posted on 2025-05-01

A：喜闻乐见的题

题意：

给定两圆，以其中一个圆内为中心作正方形完全在这个圆内的条件，正方形完全在另一个圆的条件概率；

思路：

由条件概率公式$$P(B|A)=\frac{P(AB)}{P(A)}$$,我们只需要求出$$P(AB)$$和$$P(A)$$即可；

$$P(A)$$的求解：正方形中心可行域为以$$A$$为圆心，$$\frac{\sqrt{4r_1^2-d^2}-d}{2}$$为半径的圆，输入保证这个半径长度不为$$0$$；

$$P(BA)$$的求解：由以上的分析，正方形的中心也在以$$B$$为圆心，$$\frac{\sqrt{4r_2^2-d^2}-d}{2}$$的圆内（注意输入没有保证，要特判不存在的情形），因此正方形的中心可行域为两圆的相交区域，问题转化为两圆相交面积问题模板；

两圆面积交问题：

如果两圆相离、外切、内切或者内含，那么他们的面积交为0；
如果两圆相交，可以通过容斥原理转化为两个扇形面积减去两个三角形的面积；
由于三角形的顶点为两圆交点并不方便求解，可以考虑采用$$Heron$$公式；

B: 此曲一响，_______________

题意：

给定多边形$$Polygon$$和点$$T，S$$,求多边形内部到$$S$$的距离不超过到点$$T$$的距离的$$k$$倍的所有点构成区域面积；

思路：

到两定点比值一定的轨迹构成$$Apollonius$$圆；

其中，两定点和与定点共线的直径的两个对径点共同构成调和点列，通过这个性质可以快速求出$$Apollonius$$圆的半径和圆心（注意题目输入保证是不会让圆退化为中垂线的）；

问题转化为多边形与圆面积交模板：

以圆的圆心为视点，对多边形作三角剖分；
一点为圆心的三角形与圆面积交分为四种情况：
- 所对线段两点完全在圆内，此时面积交为整个三角形；
- 如果线段两端点有以一个在圆外一个在圆内，那么面积交为一个三角形和一个扇形
- 如果线段两端点两个端点均在圆外且线段与圆没有交点（或相切），那么面积交为一个扇形；
- 如果线段两端点两个端点均在圆外且线段与圆有交点，那么面积交为一个三角形加两个
  
  扇形；
- 注意这里涉及反三角函数的转化，如果出现点重合的情况一定要特判为0，否则可能会出现$$nan$$
整个多边形与圆面积交为各个三角形与圆面积交的有向和；

E: 麦田怪圈II

题意：

求出内外切于两圆之间的前$$n$$个最大圆面积和；

思路：

以两圆切点为反演中心，$$1$$为反演半径作反演变换；

两圆化成平行两直线，要求的$$n$$个圆直径均为两平行直线的距离，由反演变化距离公式以及圆幂定理，设反演中心$$I$$和左（右）手第$$k$$个圆圆心连线交点为$$C,D$$，那么反演变换前该圆的直径$$2r[k]=C’D’=\frac{CD}{IC \cdot ID}=\frac{(r_2-r_1)r_1r_2}{k^2(r_2-r_1)^2+r_1r_2}$$，面积总和即为$$\sum_{k=1}^{n}\pi[k/2][k/2]$$；

注意这里$$k,n$$应该要开long long ~~否则整形的精度将会溢出导致半径为负~~；

F: 麦田怪圈III

题意：

给定$$n$$个圆，判断原点是否在它们的「包围圈」内，所谓「包围圈」是指由它们的本身和两两外公切线所围成最大的凸集；

思路：

不难发现原点到各个圆的两条公切线是问题关键，（当然如果没有的话问题答案即为YES），对每一条切线的极角排序（无需分象限），如果有相邻的极角之差超过$$\pi$$，那么答案便是NO；

第$$i$$个圆的两条切线的极角$$\theta=atan2(y_i,x_i)\pm asin(\frac{r_i}{\sqrt{x_i^2+y_i^2}})$$;

I: 过马路

题意：

求运动的多边形和动点不相遇的最长持续时间；

思路：

（题解的正确性存疑，因为本人$$hack$$过自己的几组边界数据但是提交却出现$$AC$$的情况，本人也认为思路不完全正确）；

考虑转化运动参考系，将多边形当作惯性系，那么动点$$x$$向速度恒为$$v$$,$$y$$向速度不大于$$u$$,如果初始状态多边形的点全部都在射线$$y=\frac{ux}{v}$$的一侧，那么动点无需等待全力过马路即可，时间为$$w/u$$,否则等待一段时间，这段时间是每个点作方向为$$(v,u)$$的「切线」最右侧所代表的时间，换言之，$$T=max_{1\le i\le n}(\frac{x}{v}-\frac{y}{u})$$，再全速前进即可；

N：回转数

题意：

求给定点关于给定多边形的回转数；

思路：

为降低时间开销不考虑极角排序做法；

遍历每一条边，判断边$$uv$$与点$$a$$的相对位置关系；

回转数自增当且仅当

$$(v-u)\times(a-u)>0$$
$$u.y\le a.y$$
$$a.y<v.y$$

回转数自减当且仅当

$$(v-u)\times(a-u)<0$$
$$u.y\ge a.y$$
$$a.y>v.y$$

S: 兔儿爷（Simple Version）

题意：

判断点是否在三角形的内部；

思路：

本题是$$T$$题的$$n=3$$ 的版本；

T: 兔儿爷（Easy Version）

题意：

判断点是否在多边形的内部（多边形可能会退化，也不一定是凸的）；

思路：

本题由两个模板组成；

$$Graham$$算法求给定点集的凸包
- 选定二维偏序最小者为极点
- 剩余的点作极角排序
- 维护单调栈，逆时针第一条边入栈，若新加入的点在栈顶边的右侧则出栈，否则直接入栈，始终保证栈内至少有两个点（一条边）；
二分极角序判断点是否在凸多边形内
- 选取二维偏序最小者为极点
- 三角剖分多边形，二分对角线位置，判断在最大在何处对角线的左侧
- 判断是否在两条对角线夹边内部
注意事项：
1. 退化情况包括$$n=1,n=2$$
2. 点在对角线或者一边的延长线上，此时不能算作在多边形的内部；

A： 喜闻乐见的题

题意：

思路：