集训之几何专题

A

题意简述

给你两个圆，A 和 B。在圆 A 中随机选取一个点。定义事件 C 代表能在 A 中画一个边长为 $d$ 的圆，使得该正方形都在圆 A 内，且以 P 为中心。定义事件 D 代表能在 B 中画一个边长为 $d$ 的圆，使得该正方形都在圆 B 内，且以 P 为中心。

求出 P(B|A)。

题目分析

首先考虑正方形与一个圆相切的情况，此时 P 到圆心的距离为 $\sqrt{r^2 - \dfrac{d^2}{4} - \dfrac{d}{2}}$，发现这就是边界情况，而 P 点可以在以此为半径的园内。所以剩下的就是求两圆的面积交。

注意还有特判一下边界情况即可。

B

题意简述

给你一个多边形，再给你一个圆（由题目转化而来），求两个图形的面积并。

题目分析

首先一个多边形可以被划分成多个以圆心为中心点的三角形，所以我们只需要考虑子问题，每个三角形与一个圆的面积交（注意这里可以是负数）为多少，其和即是答案。

求三角形与圆的面积交，因为三角形有一个点是圆心，所以我们只考虑另两个点 A, B，先求出线段 AB 与圆的交点，将交点和 A, B 都添加到一个集合中，按照一条直线上相对顺序排好序。考虑计算相邻两个点形成的面积，若有一个点在圆外，那么形成的面积必然是扇形面积，所以求一下角度计算面积即可；若都在圆内或圆上，则形成的面积是三角形，用叉乘计算面积即可。

E

题意简述

先给定两个圆相切（不重合），然后有无数个圆在两圆缝隙内与圆相切，且这些圆两两相切。求其中最大的 $n$ 个圆的面积和。

题目分析

考虑反演，根据反演性质，原来相切的图形也一定相切。所以可以得到上图的图形。

设反演半径为 $1$，两条竖线的横坐标很好求出为 $\dfrac{1}{2r}$。由此很容易得到相切黄色小圆的半径 $\dfrac{\frac{1}{2r_1} - \frac{1}{2r_2}}{2}$，剩下的就是循环 $n$ 次，算出黄色小圆到 P 点的距离，然后反演回去得到原来的圆半径即可。

反演公式：记圆 A 半径为 $r_1$，反演图形 B 半径为 $r_2$，则有：

$$r_2 = \dfrac{1}{2}(\dfrac{1}{|OA| - r_1} - \dfrac{1}{|OA| + r_1})R^2$$

F

题意简述

给你 $n$ 个圆，询问是否能在平面中找到 $3$ 个点，其中每个点都在至少一个圆内，且满足其组成的几何图形包含原点。

题目分析

首先有一个圆能够包含原点那肯定可行，下面讨论不包含原点的情况。

我们发现此时原点到圆的切点是极端情况。进而发现，如果我们求出这 $2n$ 条切线的的角度，然后按角度排序，看是否存在相邻两个角度满足大于 $\pi$，如果存在，那么可以发现一定是找不到这样的 3 个点的；如果不存在，那么可以发现一定是可以找到这样的 3 个点的。

I

题意简述

给你一个凸多边形和一个起始点（原点），已经一个速度向量 $(u, v)$，满足 $u > 0, v > 0$，询问从原点出发，在不与多边形相撞（可以擦边）的情况下，最快多久能到达 $y = w$，注意你的横坐标速度一定是 $u$，但你的纵坐标速度可以比 $v$ 小。

题目分析

首先判断向量 $(u, v)$ 所在直线是否与多边形相交，如果不相交（或只是擦边）直接以最大速度走即可。如果相交，我们可以采取策略，让一开始的纵坐标速度为 $0$，等待一个时刻出发使得此时以最大速度出发刚好能擦边。

这个东西可以二分，也可以 $O(n)$ 判断，只需要遍历每个点，假设这个点是切点，以此点做一条方向为 $(u, v)$ 的切线，判断所有点是否都在左边或直线上（因为是凸多边形，所以只用判断两边）即可。

S

题意简述

给你 3 个点 $(x_1, y_1), (x_2, y_2), (x_3, y_3)$，$q$ 次询问，每次询问给定 $(x, y)$，询问是否存在一种方案，满足 $ax_1 + bx_2 + cx_3 = x \land ay_1 + by_2 + cy_3 = y \land a + b + c = 1\land a, b, c \ge 0$。

题目分析

由结论，凸组合能组成的向量的终点都是在这些点的凸包中。所以我们只需要求一下凸包，然后判断点是否在凸包内即可。

而这道题只有 $3$ 个点，所以分情况，看是退化成点，线，还是三角形，然后判断是否在各自图形里面即可。