1 CF613A 扫雪机
2 题目描述
时间限制 \(2s\) | 空间限制 \(256M\)
\(Peter\) 的新年礼物是一台全新的扫雪机，他拿到手后马上就决定试试看。看了说明书发现这个扫雪机和普通的扫雪机不一样，这个扫雪机必须固定在某一个点（这个点不在扫雪机覆盖的下面）上再打开，这样扫雪机开始旋转，然后清除掉经过路线上的所有的雪。我们假设 \(Peter\) 的扫雪机是平面上的一个多边形，在扫雪机打开后就围绕着固定点做圆周运动。也就是说这个多边形的边和内部的每个点都绕着固定的点做圆周运动。\(Peter\) 决定把扫雪机固定在点 \(P\)，他现在想知道扫雪的面积是多少。
数据范围：\(1 ≤ n ≤ 100000\)
3 题解
我们很容易想到：这个多边形扫过的面积是一个圆环形。那么我们只需要找出这个圆环最外边的圆的半径与最里面的圆的半径，将两者平方的差乘上 \(\pi\) 即可。推导：最大的圆的面积为 \(\pi r_1^2\)，最小的圆的面积为 \(\pi r_2^2\)，圆环的面积为两者的差，即 \(\pi r_1^2 - \pi r_2^2\)。提取 \(\pi\) 这个公因子，得：\(\pi (r_1^2 - r_2^2)\)。
这时，我们很容易可以得出一个做法：利用距离公式 \(dis = \sqrt {(x_2 - x_1) ^2 + (y_2 - y_1)^2}\) 计算出每个点与点 P 之间的距离，然后取其中的最大值和最小值即可。很不幸的是，这个做法存在严重的问题：在某些情况下，最小的圆并不是由点绕 P 旋转得出的，而是由一条边绕点 P 得出的。这是因为，一条边在旋转过程中形成的圆的半径是点 P 到它的垂线，如果这条垂线的长度小于离点 P 最近的点与点 P 的长度，那么最小的圆就是由这条线段贡献的。
首先，题目中提到所有的边都是按照给出点的顺序顺次连接的，所以一共的边数为 \(n\) 条，完全可以遍历一遍进行计算，时间复杂度为 \(O(n)\)。我们接下来考虑，对于每两个点来说，经过这两个点的一次函数的解析式是什么：对于经过点 \((x_1, y_1)\)，\((x_2, y_2)\) 的解析式 \(f(x) = kx + b\)，我们可以列出方程组：
\(\begin{cases}kx_1 + b = y_1 \space \space \space \space \space \space 1\\kx_2 + b = y_2 \space \space \space \space \space \space 2\end{cases}\)
用 \(1\) 式减 \(2\) 式，得：\(k = \dfrac{y_1 - y_2}{x_1 - x_2}\)，\(b = y_1 - kx_1 = y_1 - \dfrac{y_1 - y_2}{x_1 - x_2}x_1\)。
因此，该函数的解析式为 \(f(x) = \dfrac{y_1 - y_2}{x_1 - x_2} x + y_1 - \dfrac{y_1-y_2}{x_1 - x_2}x_1\)。
这里我们有一个性质：两个一次函数如果互相垂直，那么它们的斜率之积为 \(-1\)。具体证明如下：
设 \(f(x) = kx\)，\(g(x) = k'x\)，函数 \(f(x)\) 与 \(x\) 轴的夹角为 \(\alpha\)，函数 \(g(x)\) 与 \(x\) 轴的夹角为 \(\alpha + 90^{\circ}\)，那么这两个函数明显互相垂直。
此时我们发现：\(\tan{\alpha} = \dfrac{y}{x} = k\)，\(\tan(\alpha + 90^{\circ}) = \dfrac{y}{x} = k'\)。也就是说，只要证明 \(\tan(\alpha + 90^{\circ}) = - \dfrac{1}{\tan\alpha}\) 就可以证明 \(k' = -\dfrac{1}{k}\)了。
证明：\(\tan(\alpha + 90^{\circ}) = \dfrac{\sin(\alpha + 90^{\circ})}{\cos(\alpha + 90^{\circ})} = \dfrac{\cos\alpha}{-\sin \alpha} = - \dfrac{1}{\tan \alpha}\)
\(\space \space \space \space \space \space\space \space \space \space \space \space\space \space \space \space \space \space\space \space \space \space \space \space\space \space \space \space \space \space\space \space \space \space \space \space\therefore k' = -\dfrac{1}{k}\)
因为两个函数是否垂直只与其斜率有关，所以如果函数 \(f(x) = kx + b\) 和 \(g(x) = k'x + b'\) 垂直，那么必然有 \(k' = -\dfrac{1}{k}\)。
由此，我们可以算出与经过 \((x_1, y_1), (x_2, y_2)\) 两点的函数垂直的函数的斜率，设其截距为 \(b'\)，则其解析式为：\(g(x) = \dfrac{x_2 - x_1}{y_1 - y_2}x + b'\)。接下来，我们只需要找到 \(f(x)\) 和 \(g(x)\) 这两个函数的交点，即确定出 \(g(x) = f(x)\) 的 \(x\) 即可。因此，我们可以列出方程：
\[\dfrac{x_2 - x_1}{y_1 - y_2}x + b' = \dfrac{y_1 - y_2}{x_1 - x_2} x + y_1 - \dfrac{y_1-y_2}{x_1 - x_2}x_1 \]又因为 \(g(x)\) 经过点 P\((x_p, y_p)\)，所以我们可以列出方程组：
\[\begin{cases} \dfrac{x_2 - x_1}{y_1 - y_2}x + b' = \dfrac{y_1 - y_2}{x_1 - x_2} x + y_1 - \dfrac{y_1-y_2}{x_1 - x_2}x_1 \\ \\ \dfrac{x_2 - x_1}{y_1 - y_2}x_p + b'= y_p \end{cases} \]化简可得：
$
\begin{aligned}
b' &= y_p - \dfrac{x_2 - x_1}{y_1 - y_2}x_p \newline
\dfrac{x_2 - x_1}{y_1 - y_2}x + y_p - \dfrac{x_2 - x_1}{y_1 - y_2}x_p &= \dfrac{y_1 - y_2}{x_1 - x_2}x + y_1 - \dfrac{y_1-y_2}{x_1 - x_2}x_1 \newline
\dfrac{x_2 - x_1}{y_1 - y_2}x - \dfrac{y_1 - y_2}{x_1 - x_2}x &= y_1 - y_p + \dfrac{x_2 - x_1}{y_1 - y_2}x_p -\dfrac{y_1-y_2}{x_1 - x_2}x_1 \newline
(\dfrac{x_2 - x_1}{y_1 - y_2} - \dfrac{y_1 - y_2}{x_1 - x_2})x &= y_1 - y_p + \dfrac{x_2 - x_1}{y_1 - y_2}x_p -\dfrac{y_1-y_2}{x_1 - x_2}x_1 \newline
x &= \dfrac{y_1 - y_p + \dfrac{x_2 - x_1}{y_1 - y_2}x_p -\dfrac{y_1-y_2}{x_1 - x_2}x_1}{\dfrac{x_2 - x_1}{y_1 - y_2} - \dfrac{y_1 - y_2}{x_1 - x_2}} \newline
\end{aligned} $
此时 \(g(x)\) 的解析式为 \(g(x) = \dfrac{x_2 - x_1}{y_1 - y_2}x + y_p - \dfrac{x_2 - x_1}{y_1 - y_2}x_p\)。将 \(x\) 代入，得：
\(y = \dfrac{x_2 - x_1}{y_1 - y_2} \times \dfrac{y_1 - y_p + \dfrac{x_2 - x_1}{y_1 - y_2}x_p -\dfrac{y_1-y_2}{x_1 - x_2}x_1}{\dfrac{x_2 - x_1}{y_1 - y_2} - \dfrac{y_1 - y_2}{x_1 - x_2}} + y_p - \dfrac{x_2 - x_1}{y_1 - y_2}x_p\)。
也就是说，此时垂足的坐标为：
\((\dfrac{y_1 - y_p + \dfrac{x_2 - x_1}{y_1 - y_2}x_p -\dfrac{y_1-y_2}{x_1 - x_2}x_1}{\dfrac{x_2 - x_1}{y_1 - y_2} - \dfrac{y_1 - y_2}{x_1 - x_2}}, \dfrac{x_2 - x_1}{y_1 - y_2} \times \dfrac{y_1 - y_p + \dfrac{x_2 - x_1}{y_1 - y_2}x_p -\dfrac{y_1-y_2}{x_1 - x_2}x_1}{\dfrac{x_2 - x_1}{y_1 - y_2} - \dfrac{y_1 - y_2}{x_1 - x_2}} + y_p - \dfrac{x_2 - x_1}{y_1 - y_2}x_p)\)
我们此时只需要计算垂足和点 P 之间的距离，将其与某个点到点 P 最小值比较即可（最大值一定是点 P 与某节点的距离）。
注意：当 \(x_1 = x_2\) 时，\(f(x)\) 不是函数，需要特判：此时垂足坐标为 \((x_1, y_p)\)。当 \(y_1 = y_2\) 时，\(g(x)\) 不是函数，需要特判：此时垂足坐标为 \((x_p, y_1)\)。而且，当垂足不在该线段上，而是在线段的延长线上时，不应该计入答案中，需要特判垂足横坐标与纵坐标是否都大于等于线段两端点中横纵坐标的最小值且小于等于线段两端点中横纵坐标的最大值。
由于答案为平方的差与 \(\pi\) 的积，而距离公式中又带有根号，我们可以将二者抵消：计算两点距离时不加根号，输出答案中直接输出最大值和最小值的差与 \(\pi\) 的积。
4 代码（空格警告）：
#include <iostream>
#include <iomanip>
using namespace std;
const int N = 1e5+10;
const double Pi = 3.141592653589793238462643383;
#define int double
int n, Px, Py, cx, cy;
int x[N], y[N];
int maxn, minn;
signed Pair;
int dis(int ax, int ay, int bx, int by) {return (ax - bx) * (ax - bx) + (ay - by) * (ay - by);}
signed main()
{
cin >> n >> Px >> Py;
for (signed i = 1; i <= n; i++) cin >> x[i] >> y[i];
minn = 0x3f3f3f3f3f3f3f3f;
maxn = 0;
for (signed i = 1; i <= n; i++)
{
maxn = max(maxn, dis(Px, Py, x[i], y[i]));
minn = min(minn, dis(Px, Py, x[i], y[i]));
}
for (signed i = 1; i <= n; i++)
{
if (i == 1) Pair = n;
else Pair = i - 1;
if (x[Pair] == x[i])
{
cx = x[i];
cy = Py;
}
else if (y[Pair] == y[i])
{
cx = Px;
cy = y[i];
}
else
{
cx = (y[Pair] - Py + (x[i] - x[Pair]) / (y[Pair] - y[i]) * Px - (y[Pair] - y[i]) / (x[Pair] - x[i]) * x[Pair]) / ((x[i] - x[Pair]) / (y[Pair] - y[i]) - (y[Pair] - y[i]) / (x[Pair] - x[i]));
cy = (x[i] - x[Pair]) / (y[Pair] - y[i]) * (y[Pair] - Py + (x[i] - x[Pair]) / (y[Pair] - y[i]) * Px - (y[Pair] - y[i]) / (x[Pair] - x[i]) * x[Pair]) / ((x[i] - x[Pair]) / (y[Pair] - y[i]) - (y[Pair] - y[i]) / (x[Pair] - x[i])) + Py - (x[i] - x[Pair]) / (y[Pair] - y[i]) * Px;
}
if (cx < min(x[Pair], x[i]) || cx > max(x[Pair], x[i])) continue;
if (cy < min(y[Pair], y[i]) || cy > max(y[Pair], y[i])) continue;
minn = min(minn, dis(Px, Py, cx, cy));
}
cout << fixed << setprecision(16) << (maxn - minn) * Pi;
return 0;
}