前言

这个月没什么好分享的了，干脆就把自己通过计算几何的计算过程来学 markdown 和 $\LaTeX$ 时写的文章从洛谷 第二次 转投这里。

第一次是在能让人绝望的 CSDN 里投的，现在想想完全不如在 AcWing 分享好。所以已经删掉了。虽然这里也可能还是有借鉴不带出处的情况出现，但反正无所谓，源和思路都开了，现在就任其恣意 抄袭 吧。

然而在此之前，我还有一件事要说——

什么杂七杂八的网站我就懒得管了，但在第一次公开发布文章的洛谷看见了，我还是非常不想吐槽洛谷的管理员把我自己修了两次的文章批掉，另写了一篇题解，却完全 不引用 的做法。即使不是大学生，也多少要有点著作权意识吧。哪天被查抄的是你以后自己“写好”的论文，我看你以后怎么办？

对了，也正是 因为不好维权，所以抄袭成风。这就进一步成为我们的 AI 做不过 ChatGPT、我们的开源生态总是失败的又一个因素。

哦还有，这场 Codeforces 之所以 unrate 也是因为出题人“借鉴了”一道题目的思路而被外国人扒了出来。

这里附上自己所看见的 “影子”。

还有管理员的文章。我别的不要，其他人也不需要主动对线浪费自己的时间和精力，如果你在某种情况下又再次看到了这里记得来道歉:) 看不到的话以后总有人会拿这篇文章说事的，即使 我强调过不要主动对线。

具体使用到的细节转换了讲法。但是作为偶然或者必然间看到的材料，我认为，完全有必要指出出处。因为这是 别人先想到的思路而不是你先想到的。

你只是通过各种各样的途径看到然后拿来主义罢了。单凭没有说明清楚就写了文章的这点，我只能表示怀疑以及非常的遗憾。希望下次自己自私一点，不要再写这种无利可图的文章了。

下面是我第一次投稿的时间。

活着很累的，能写一篇文章说说内心的感受或者思考问题的心路历程都是一种 奢侈的浪费。

临近期末外加决定是否继续学业的年纪，头痛到不管哪一门语言的代码都不想碰。不过还是要感谢这个学期，让我学会了盲打键盘并见到了一堆极其难绷的事情。反正，剩下的内容就是正文了。总之我还要留一个:)。

题面翻译

大意

以逆时针顺序给出笛卡尔平面上 $n (4 \leqslant n \leqslant 5000)$ 个点 $A_1,A_2,\ldots,A_n$ 的坐标，从而确定一凸多边形。该凸多边形的性质有如下保证：
1. 所有点的坐标均为整数且 $-10^{9} \leqslant x,y \leqslant 10^{9}$ 。
2. 对于该凸多边形的任意内角 $\alpha$ ，均有 $90^{\circ} \leqslant \alpha < 180^{\circ}$ 。

现从凸多边形的任意两边上分别取出两点，将所有由两点所确定的、长度不超过 $1$ 的弦所经过的凸多边形内部区域标红。求标红区域的面积。

输入格式

第一行输入 $n$ 。

之后 $n$ 行每行给出 $1$ 个点的坐标。

输出格式

只输出标红区域的面积，保留 $11$ 位小数。误差不超过 $10^{-4}$ 即视为正确。

没错，我就是译者。

正文

首先要说明的是这道题，代码实现并不是太难，难的是推式子还有调试。我会试着把过程讲解得尽可能细致。当然如有问题还请不吝指出，我会尽力和大伙一起解决的。

大致所需知识

• 曲线上点坐标的参数方程表示。
• 函数图像变换。
• 三角函数积化和差与和差化积公式。
• 定积分。
• 二分求根。

程序构建脉络

题目的描述已经很清楚了，对于这类考数学推演运算而不是数据结构或者纯算法的题目，我个人一开始的想法就是研究样例是怎样的。

先优先考虑凸多边形各边长度 均大于 $1$ 的情况。注意到弦长为 $1$ 的弦只会出现在凸多边形的两邻边之间。这启发我们：算出每一个角然后用角度计算相应面积即可。

我们先来看看单个符合要求 $(90^{\circ}\leqslant \alpha <180^{\circ})$ 的角 $\alpha$。

按照题目限制下的逻辑，可以想象一个长度为 $1$ 的刚性杆从边 $\text{BD}$ 顺畅地滑到边 $\text{BE}$。整个过程中，杆所经过的区域即为我们的目标。

显然由滑动的过程以及圆自身的性质可知，曲线绝不会是圆弧。那么此刻，问题转化为求出杆运动所生成包络线的函数表达式及其积分。

由于我们只在逻辑上知道这条线性质如何如何，而不知道这条线到底可以由哪一个初等的函数表出，为此，我们引入参数方程来代替相对更直观的函数表达式。

按上图，包络线明显与 $\alpha$ 有关。又注意到，在杆的运动过程中， $\theta$ 也是一直在变化的。那么我们理应使用 $\alpha$ 和 $\theta$ 作为参数方程的参数。

统一记包络线上的点为 $G$，其坐标均为 $(x,y)$ 的抽象形式。则点 $G$ 可由两参数 $\theta$ 与 $\alpha$ 表示为 $\begin{matrix}x(\theta,\alpha)\ y(\theta,\alpha)\end{matrix}$。同时，直线 $l_{HI}$ 的方程可经以下推导得出。

在 $\triangle \text{HIB}$ 中，由正弦定理得到 $\dfrac{x_\text{I}}{\sin(\pi-\theta-\alpha)}=\dfrac{\text{HI}}{\sin\alpha}$，那么，进一步就可以有 $\dfrac{x_\text{I}}{\sin(\theta+\alpha)}=\dfrac{1}{\sin\alpha}$。

从而，我们可以得到以下结果。

$$ \begin{aligned}
&\Rightarrow x_\text{I}=\dfrac{\sin(\theta+\alpha)}{\sin\alpha},y_\text{J}=\dfrac{\sin(\theta+\alpha)}{ \sin\alpha}\tan\theta
\\& \therefore \ l_\text{HI}:\dfrac{\sin\alpha \cdot x}{\sin(\theta+\alpha)}+\dfrac{\sin\alpha \cdot y}{\tan\theta\sin(\theta+\alpha)}=1
\end{aligned}$$

我们还可从包络线切线的性质出发，得到 $l_\text{HI}$ 的斜率。注意，按照图上的标法，斜率需要加负号。这里再提供另一种不需要管斜率，算起来相对更简单的推导过程。

此处不以题解中显示的锐角 $\theta$ 作为参数，而是以其补角作为 以下的参数 $\theta$。

参数方程部分：
$$\begin{aligned}&\dfrac{x_\text{I}}{\sin(\theta-\alpha)}=\dfrac{1}{\sin\alpha},y_\text{J}=-\tan\theta \cdot x_\text{I}\\
\\ \Rightarrow & x_\text{I}=\dfrac{\sin(\theta-\alpha)}{\sin\alpha}
, y_\text{J}=-\dfrac{\sin(\theta-\alpha)}{\sin\alpha}\tan\theta
\\
\\l:&\dfrac{x(\theta,\alpha)}{x_\text{I}}+\dfrac{y(\theta,\alpha)}{y_\text{J}}=1,\ \dfrac{\mathrm{d}y}{\mathrm{d}x}=\dfrac{y_\theta}{x_\theta}=\tan\theta
\\ \Rightarrow & -\tan\theta\cdot x(\theta,\alpha)+y(\theta,\alpha)=-\dfrac{\sin(\theta-\alpha)}{\sin\alpha}\tan\theta
,\ y_\theta=\tan\theta \cdot x_\theta
\\
\therefore &-\dfrac{x(\theta,\alpha)}{\cos^2\theta}-x_\theta\tan\theta+y_\theta=\csc\alpha(-\cos(\theta-\alpha)\tan\theta-\sin(\theta-\alpha)\sec^2\theta)\\
\\\Rightarrow &-\dfrac{x(\theta,\alpha)}{\cos^2\theta}=
-\dfrac{\sin(\theta-\alpha)+\sin\theta\cos\theta\cos(\theta-\alpha)}{\sin\alpha\cos^2\theta}
\\\Rightarrow &x(\theta,\alpha)=\dfrac{\sin(\theta-\alpha)+\sin\theta\cos\theta\cos(\theta-\alpha)}{\sin\alpha},y(\theta,\alpha)=\dfrac{\sin^2\theta\cos(\theta-\alpha)}{\sin\alpha}
\end{aligned}
$$
积分部分：
$$\begin{aligned}
x_\theta&=\csc\alpha[\cos(\theta-\alpha)+\cos2\theta\cos(\theta-\alpha)-\dfrac{1}{2}\sin2\theta\sin(\theta-\alpha)]
\\ \therefore
\text{S}&=\int_\alpha^\pi y(\theta,\alpha)\cdot x_\theta\mathrm{d}\theta
\\
\Rightarrow \text{S}&=\csc^2\alpha\int_\alpha^\pi\sin^2\theta\cos(\theta-\alpha)[(1+\cos2\theta)\cos(\theta-\alpha)-\dfrac{1}{2}\sin2\theta\sin(\theta-\alpha)]\mathrm{d}\theta
\\&=
\dfrac{\csc^2\alpha}{4}\int_\alpha^\pi 8\cos^2\theta\sin^2\theta\cos^2(\theta-\alpha)-\sin^2\theta\sin2\theta\sin(2\theta-2\alpha)\mathrm{d}\theta
\\&=
\dfrac{\csc^2\alpha}{4}\int_\alpha^\pi 2\sin^22\theta\cos^2(\theta-\alpha)-\sin^2\theta\sin2\theta\sin(2\theta-2\alpha)\mathrm{d}\theta
\\&=
\dfrac{\csc^2\alpha}{4}\int_\alpha^\pi \sin^22\theta+\sin^22\theta\cos(2\theta-2\alpha)-\sin^2\theta\sin2\theta\sin(2\theta-2\alpha)\mathrm{d}\theta
\\&=
\dfrac{\csc^2\alpha}{8}\int_\alpha^\pi 1-\cos4\theta+
(1-\cos4\theta)\cos(2\theta-2\alpha)-(1-\cos2\theta)\sin2\theta\sin(2\theta-2\alpha)\mathrm{d}\theta
\\&=
\dfrac{\csc^2\alpha}{16}\int_\alpha^\pi 2-2\cos4\theta+
2\cos(2\theta-2\alpha)-2\cos4\theta\cos(2\theta-2\alpha)
-(1-\cos2\theta)(\cos(-2\alpha)-\cos(4\theta-2\alpha))
\mathrm{d}\theta
\\&=
\dfrac{\csc^2\alpha}{16}\int_\alpha^\pi 2-2\cos4\theta+
2\cos(2\theta-2\alpha)-\cos(6\theta-2\alpha)-\cos (2\alpha+2\theta)
-\cos2\alpha+\cos(4\theta-2\alpha)
+\cos2\theta\cos2\alpha-\cos2\theta\cos(4\theta-2\alpha)
\mathrm{d}\theta
\\&=
\dfrac{\csc^2\alpha}{32}\int_\alpha^\pi 4-4\cos4\theta+
4\cos(2\theta-2\alpha)-2\cos(6\theta-2\alpha)-2\cos (2\alpha+2\theta)
-2\cos2\alpha+2\cos(4\theta-2\alpha)
+2\cos2\alpha\cos2\theta-\cos(6\theta-2\alpha)-\cos(2\theta-2\alpha)
\mathrm{d}\theta
\\&=
\dfrac{\csc^2\alpha}{32}\int_\alpha^\pi 4-4\cos4\theta+
4\cos(2\theta-2\alpha)-3\cos(6\theta-2\alpha)-\cos (2\alpha+2\theta)
-2\cos2\alpha+2\cos(4\theta-2\alpha)
\mathrm{d}\theta
\\&=
\dfrac{\csc^2\alpha}{64}\int_\alpha^\pi 8-8\cos4\theta+
8\cos(2\theta-2\alpha)-6\cos(6\theta-2\alpha)-2\cos (2\alpha+2\theta)
-4\cos2\alpha+4\cos(4\theta-2\alpha)
\mathrm{d}\theta
\\
\Rightarrow \text{S}&=\left. \dfrac{\csc^2\alpha}{64}(8\theta-2\sin4\theta+4\sin(2\theta-2\alpha)-\sin(6\theta-2\alpha)-\sin(2\theta+2\alpha)
-4\cos2\alpha\cdot\theta+\sin(4\theta-2\alpha))\right|_{\alpha}^{\pi}
\end{aligned} $$

注记：
1. 对于不包含交点的面积，需要再加上 $\dfrac{1}{2}\sin\alpha\cos\alpha$。
2. 对于含有交点的部分，只需换 $\alpha$ 为二分套二分求得的 $\theta_i$ 即可。

$$-\tan\theta=\dfrac{\mathrm{d}y}{\mathrm{d}x}=\dfrac{\mathrm{d}y(\theta,\alpha)}{\mathrm{d}x(\theta,\alpha)}$$

还观察到当两向量给定时，其夹角 $\alpha$ 也便随之确定。所以此时的斜率可认为只与 $\theta$ 有关。那么：

$$-\tan\theta=\dfrac{y_\theta}{x_\theta}\Rightarrow y_\theta=-\tan\theta \cdot x_\theta$$

其中 $y_\theta,x_\theta$ 分别表示 $y(\theta,\alpha),x(\theta,\alpha)$ 对 $\theta$ 求偏导。联立直线方程与斜率导出式有如下方程组。

$$
\left\{\begin{matrix}
\dfrac{\sin\alpha \cdot x(\theta,\alpha)}{\sin(\theta+\alpha)}+\dfrac{\sin\alpha \cdot y(\theta,\alpha)}{\tan\theta\sin(\theta+\alpha)}=1
\\ \\ y_\theta=-\tan\theta \cdot x_\theta
\end{matrix}\right.
$$

对第一式化简整理，等式两边同时对 $\theta$ 求偏导，与第二式的条件一起，即可求出参数方程。具体步骤如下。
$$
\begin{aligned}
&\tan\theta \cdot x(\theta,\alpha)+y(\theta,\alpha)=\dfrac{\tan\theta\sin(\theta+\alpha)}{\sin\alpha}
\\&\Rightarrow \dfrac{x(\theta,\alpha)}{\cos^2\theta}+\tan\theta \cdot x_\theta+y_\theta=\frac{\tan\theta\cos(\theta+\alpha)}{\sin\alpha}+\dfrac{\sin(\theta+\alpha)}{\sin\alpha\cos^2\theta}
\\&\Rightarrow x(\theta,\alpha)+\overbrace{\tan\theta \cdot x_\theta+y_\theta}^0=\dfrac{\sin(\theta+\alpha)+\sin\theta \cos\theta \cos(\theta+\alpha)}{\sin\alpha}
\\&\Rightarrow y(\theta,\alpha)=\dfrac{\tan\theta\sin(\theta+\alpha)}{\sin\alpha}-\dfrac{\tan\theta\sin(\theta+\alpha)+\sin^2\theta\cos(\theta+\alpha)}{\sin\alpha}
\\
\\
& \therefore
\left\{\begin{matrix}
\begin{aligned}
&x(\theta,\alpha)=\dfrac{\sin2\theta\cdot \cos(\theta+\alpha)+2\sin(\theta+\alpha)}{2\sin\alpha}
\\&y(\theta,\alpha)= -\dfrac{\sin^2\theta\cdot \cos(\theta+\alpha)}{\sin\alpha}
\end{aligned}
\end{matrix}\right.
\end{aligned}
$$
然后重点来了，我们要求的是面积，而得到的只是参数方程。接下来怎么办？其实也还好，我们带进去硬解就完了。要求面积，就必须先知道参数的范围。我们可以由图上的关系，轻松得出 $\theta \in [0,\pi-\alpha]$。既然上下限已知，那我们可以动手了。对于参数方程，求面积一般有以下形式。

$$
\text{S}=\int y(t_1,t_2,\ldots,t_n)\mathrm{d}[x(t_1,t_2,\ldots,t_n)]
$$
其中 $t_1,t_2,\ldots,t_n$ 代表参数。当只有一个参数变化，其它参数保持不变时，即可使用链式法则积分之。对本道题而言，有下面的形式。
$$
\text{S}=\int y(\theta,\alpha)\mathrm{d}[x(\theta,\alpha)]=\int y(\theta,\alpha)\frac{\partial x(\theta,\alpha)}{\partial\theta}\mathrm{d}\theta
$$
对于合乎几何逻辑的上下限，图上已经很明确了，因此可以列得下式。
$$
\text{S}=\int^{0}_{\pi-\alpha} y(\theta,\alpha)\frac{\partial x(\theta,\alpha)}{\partial\theta}\mathrm{d}\theta
$$
上式才能保证从左往右积。抽时间，或者直接找 WolframAlpha 计算整理。具体说，先输入 $x$ 的参数方程求解其关于 $\theta$ 的偏微分。得到答案后，再计算其与 $y$ 参数方程的乘积，最后再算二者乘积的不定积分即可。但总之，经由暴力计算，可以有下式。
$$
\begin{aligned}
\text{S}&=\left. \dfrac{1}{64\sin^2\alpha}
[
(8-4\cos2\alpha)\theta-2\sin4\theta+4\sin(2\theta+2\alpha)
-\sin(6\theta+2\alpha)
+\sin(2\alpha-2\theta)
+\sin(4\theta+2\alpha)]
\right|_{0}^{\pi-\alpha}
\end{aligned}
$$
同时，作为第二次提交失败而得到的反馈，这里我将给出我个人的证明。
$$
\begin{aligned}
\text{S}&=\int_{\pi-\alpha}^{0}y(\theta,\alpha)\mathrm{d}[x(\theta,\alpha)]
\\ &=\int_{0}^{\pi-\alpha}\dfrac{\sin^2\theta\cdot \cos(\theta+\alpha)}{\sin\alpha}\mathrm{d}[\dfrac{\sin2\theta\cdot \cos(\theta+\alpha)+2\sin(\theta+\alpha)}{2\sin\alpha}]
\\ &=\dfrac{1}{2\sin^2\alpha}\int_{0}^{\pi-\alpha}
\sin^2\theta\cdot \cos[\theta+\alpha](2\cos2\theta\cdot\cos(\theta+\alpha)-\sin2\theta\cdot\sin(\theta+\alpha)+2\cos(\theta+\alpha))\mathrm{d\theta}
\\ &=\dfrac{1}{2\sin^2\alpha}
\int_{0}^{\pi-\alpha}
\sin^2\theta [2\cos^2(\theta+\alpha)(1+\cos2\theta)
-\sin2\theta\sin(\theta+\alpha)\cos(\theta+\alpha)]
\mathrm{d\theta}
\\ &=\dfrac{1}{4\sin^2\alpha}
\int_{0}^{\pi-\alpha}
(1-\cos2\theta) [(1+\cos(2\theta+2\alpha))(1+\cos2\theta)
-\sin2\theta\sin(\theta+\alpha)\cos(\theta+\alpha)]
\mathrm{d\theta}
\\ &=\dfrac{1}{4\sin^2\alpha}
\int_{0}^{\pi-\alpha}
(1+\cos(2\theta+2\alpha))(1-\cos^22\theta)
-\sin2\theta\sin(\theta+\alpha)\cos(\theta+\alpha)
+\sin2\theta\cos2\theta\sin(\theta+\alpha)\cos(\theta+\alpha)
\mathrm{d\theta}
\\ &=\dfrac{1}{16\sin^2\alpha}
\int_{0}^{\pi-\alpha}
2(1+\cos(2\theta+2\alpha))(1-\cos4\theta)
-2\sin2\theta\sin(2\theta+2\alpha)
+\sin4\theta\sin(2\theta+2\alpha)
\mathrm{d\theta}
\\ &=\dfrac{1}{16\sin^2\alpha}
\int_{0}^{\pi-\alpha}
2-2\cos4\theta+2\cos(2\theta+2\alpha)-2\cos(2\theta+2\alpha)\cos4\theta
-\cos2\alpha+\cos(4\theta+2\alpha)
+\dfrac{1}{2}\cos(2\alpha-2\theta)-\dfrac{1}{2}\cos(2\alpha+6\theta)
\mathrm{d\theta}
\\ &=\dfrac{1}{32\sin^2\alpha}
\int_{0}^{\pi-\alpha}
4-4\cos4\theta+4\cos(2\theta+2\alpha)
-2\cos(6\theta+2\alpha)-2\cos(2\alpha-2\theta)
-2\cos2\alpha+2\cos(4\theta+2\alpha)
+\cos(2\alpha-2\theta)-\cos(2\alpha+6\theta)
\mathrm{d\theta}
\\ &=\dfrac{1}{32\sin^2\alpha}
\int_{0}^{\pi-\alpha}
4-4\cos4\theta+4\cos(2\theta+2\alpha)
-3\cos(6\theta+2\alpha)-\cos(2\alpha-2\theta)
-2\cos2\alpha+2\cos(4\theta+2\alpha)
\mathrm{d\theta}
\\ &=\left. \dfrac{1}{32\sin^2\alpha}
[
4\theta-\sin4\theta+2\sin(2\theta+2\alpha)-\dfrac{1}{2}\sin(6\theta+2\alpha)+\dfrac{1}{2}\sin(2\alpha-2\theta)
-2\cos2\alpha\cdot\theta+\dfrac{1}{2}\sin(4\theta+2\alpha)]
\right|_
{0}^{\pi-\alpha}
\\ &=\left. \dfrac{1}{64\sin^2\alpha}
[
(8-4\cos2\alpha)\theta-2\sin4\theta+4\sin(2\theta+2\alpha)
-\sin(6\theta+2\alpha)
+\sin(2\alpha-2\theta)
+\sin(4\theta+2\alpha)]
\right|_{0}^{\pi-\alpha}
\end{aligned}
$$

到这一步，兴许有人会问：“为什么不直接写结果呢，直接算到最后不行吗？”对此，有两点原因。一是后面也会用到这个式子，直接写成代入式会很方便。二是计算几何中喜闻乐见的精度问题，直接换成结果有时是不会 AC 的。

总之，它代表的是如图所示的面积。而为了计算的正确性，我们需要减掉直线下方那块多余的三角形面积。

由 $\sin(\pi-\alpha)=\sin\alpha,\cos(\pi-\alpha)=-\cos\alpha$ 恒等式得到三角形的面积计算式 $\text{S}_\triangle =-\dfrac{1}{2}\sin\alpha\cos\alpha$。所以，我们减去的时候就相当于加上 $\dfrac{1}{2}\sin\alpha\cos\alpha$了。

到这一步，按照上述逻辑编出来的正确代码已经可以通过样例一了。但第二个问题随之而来：为什么第二个样例跑出来的结果和给的答案对不上？

那是因为我们还没有处理重叠的部分。容易验证，当给出所有点的坐标分量都是长整数时，重叠面积只会在某边边长为 $1$ 或 $\sqrt{2}$ 时出现。这里由以下三张图辅助感性理解。

边长为 $1$ 时。

边长为 $\sqrt{2}$ 时。

边长为 $\color{red}{2}$ 时。而往后由于长度的增加，两条线一定不会相交。

而对上述结论做较为理性严谨的定性分析，可以按以下方式来看。

毕竟这道题是通过杆滑动的过程受到启发而建构起来的。我们又知道杆最终是会停在 $x$ 轴上的。加上杆的长度是 $1$，如果边的长度不是 $2$ 又严格小于 $2$，最终两根杆停下来，一定是会交叠在一起的。但从现实来看，显然不可能有一个叠着一个的情况，运动途中两杆必然发生了碰撞。那么对应回本道题，当边长严格小于 $2$ 时，便一定有相交的点。

回到相交的讨论，这里假设绿线上的坐标为 $\big(x(\theta_1,\alpha_1),y(\theta_1,\alpha_1)\big)$，变换前橙线上的坐标为 $\big(x(\theta_2,\alpha_2),y(\theta_2,\alpha_2)\big)$。第一个问题是：变换后橙线的参数方程怎么求，求完了以后怎么求出参数？

根据高中所学知识，橙线上点的坐标理应为 $\big(\text{Len}-x(\theta_2,\alpha_2),y(\theta_2,\alpha_2)\big)$。其中 $\text{Len}$ 代表凸多边形上两邻近顶点的边长。对于这一点的证明，具体来说有如下操作。

右侧的确定角度的直线可以理解为左侧的直线先平移，再关于 $y$ 轴做对称变换得到。那么对应地，曲线也是执行了上述的操作（也即平移到 $x=x_0$ 的位置后再关于 $x=x_0$ 对称）。只不过，这样容易忽略 $x$ 轴上平移的“左加右减”含义是在不加负号的前提下成立的事实，从而容易出错。

以线性代数的角度理解，上述的操作等价于对二维向量 $\boldsymbol{a}=(x,y)^T$ 施行变换 $f(\boldsymbol{a})=\boldsymbol{A}(\boldsymbol{a}+\boldsymbol{b})$，其中 $\boldsymbol{A}=\begin{pmatrix}
-1 &0 \\
0 &1
\end{pmatrix},\boldsymbol{b}=(-\operatorname{Len},0)^T$。所以有结论$\big(\text{Len}-x(\theta_2,\alpha_2),y(\theta_2,\alpha_2)\big)$。

为了求出交点对应的两个参数 $\theta_1,\theta_2$，我们发扬人类智慧，根据并利用两条曲线的单调性，从两条曲线纵坐标值的初始上界 $\sin[\min(\alpha_1,\alpha_2)]$ 与下界 $0$ 开始，以上下界所确定的中心线与曲线的交点为基准，逐步二分到与交点坐标的误差不超过 $10^{-13}$ 的位置；同时在二分缩小纵坐标误差的过程中，每次对属于 $[0,\pi-\alpha]$ 区间内的 $\theta_u$ 二分，以求得当前纵坐标为 $y_u$ 时两条曲线的对应参数。
所以，当发现边长不够 $2$ 及以上时，可以用前文得到的积分式，把积分上界换成两条曲线经由二分求出交点所对应的参数 $\theta_{u,1},\theta_{u,2}$，再减掉即可。
$$
\begin{aligned}
\text{S}&=\left. \dfrac{1}{64\sin^2\alpha}
[
(8-4\cos2\alpha)\theta-2\sin4\theta+4\sin(2\theta+2\alpha)
-\sin(6\theta+2\alpha)
+\sin(2\alpha-2\theta)
+\sin(4\theta+2\alpha)]
\right|_{0}^{\theta_{u,i}}
\end{aligned}
$$
这个时候你可能会问：“如果图形是下面这样的，我们求交点然后减掉面积，这样不会多减吗？”

对于这个担忧，由于曲线上点的坐标是由 $\theta,\alpha$ 所确定的，而对于同一个角 $\alpha_k$，若在上一次计算参数时是通过形如 $\text{Len}-x(\theta_k,\alpha_k)$ 的方式得到的话，在下一次计算时就必须得通过 $x(\theta_k,\alpha_k)$ 的方式得到，才保证不会重复。而程序按循环执行下去，只要测试数据没有锅、取模写得对，这是一定不会重复计算的。

到这里，我们仍需要由第一个样例的暗示注意到，某些矩形的宽为 $1$。这使得整个图形的面积都是标红的。好在题目的条件 $90^{\circ} \leq \alpha<180^{\circ}$ 限制了更为复杂的情况出现，所以我们只需为顶点数为 $4$ 的图形做一次特判就行了。

最后，还有两个得加以关注的点是，由于 $-10^{9} \leq x,y\leq10^{9}$, 当两个点的坐标分量 $x,y$ 都差得非常大时，用 long double 算向量模长，精度是不够的。得用 long long 才能跑过最毒瘤的那几个大样例。而这个，是我前前后后花了一个月时间才弄清楚的。

第二个是夹角的计算。我们反应最快的公式是 $\alpha=\arccos\dfrac{\boldsymbol{a}\cdot \boldsymbol{b}}{|\boldsymbol{a}|\cdot|\boldsymbol{b}|}$，但若是追求答案的精度，这也是不够用的。为了尽量降低浮点误差的累积，以 C++ 编写时，推荐使用 atan2(y,x) 函数。相应地，这会使得叉乘的应用成为必然，因为确定正切不只是需要余弦值，还需要正弦值。

代码实现

全都被 H4ck 掉了。想跑对自己想办法更正吧。

C++ 代码。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
using ll = long long;
using db = long double;
const int N = 5001;
const db eps = 1e-6, pi = acos((db)-1); 

class vec{
public:
    ll x, y;
    vec(ll xx = 0, ll yy = 0) : x(xx), y(yy) {}
    vec(const vec &a) : x(a.x), y(a.y) {}
    vec operator-(const vec &a) const { return vec(x - a.x, y - a.y); }
    db len() { return (db)sqrt(x * x + y * y); }
    vec rev() { return vec(-x, -y); }
} dot[N], edge[N];

inline db angle(vec a, vec b) {return acos(a.x * b.x / a.len() / b.len() 
                                         + a.y * b.y / a.len() / b.len());} 
                                      // atan2(a.x * b.y - a.y * b.x, a.x * b.x + a.y * b.y)

inline db interg(db theta, db alpha){ // 上下界代入式
    return ((8.0 - 4.0 * cos(2.0 * alpha)) * theta - 2.0 * sin(4 * theta) + 4.0 * sin(2.0 * (theta + alpha)) 
          - sin(2.0 * (8.0 * theta + alpha)) + sin(2.0 * (alpha - theta)) + sin(2.0 * (2.0 * theta + 3.0 * alpha)))
          / sin(alpha) / sin(alpha) / 64.0;
}

inline db overlap(db mida, db midb, db ang1, db ang2){return interg(midb, ang1) + interg(mida, ang2) 
                                                           - interg(0, ang1) - interg(0, ang2);}

void calc(db &h, db &l, db ang, db Y){ // 求两条曲线交点的参数theta
    while (fabs(h - l) > eps){
        db mid = h / 2.0 + l / 2.0;
        db yy = -pow(sin(mid), 2) / sin(ang) * cos(mid + ang);
        if (yy < Y) h = mid;
        if (yy > Y) l = mid;
    }
    return;
}
db getarea(int _n, int n, int nt){
    auto now = edge[n], lst = edge[_n], nxt = edge[nt];
    db res = 0.0, len = now.len(),
       alpha1 = angle(now, lst.rev()), alpha2 = angle(nxt, now.rev());
    if (len < 2.0){
        db la = 0.0, lb = 0.0,
           ra = pi - alpha1, rb = pi - alpha2,
           cy = sin(min(alpha1, alpha2)), fy = 0, mida, midb;

        while (fabs(cy - fy) > eps){   // 二分套二分
            db midy = cy / 2.0 + fy / 2.0;
            la = 0.0, lb = 0.0, ra = pi - alpha1, rb = pi - alpha2;
            calc(ra, la, alpha1, midy), calc(rb, lb, alpha2, midy);

            mida = la / 2.0 + ra / 2.0, midb = lb / 2.0 + rb / 2.0;
            db x1 = (sin(2.0 * mida) * cos(alpha1 + mida) + 2 * sin(mida + alpha1)) / 2.0 / sin(alpha1),
               x2 = len - (sin(2.0 * midb) * cos(alpha2 + midb) + 2 * sin(midb + alpha2)) / 2.0 / sin(alpha2);

            if (x1 < x2) cy = midy;
            if (x1 > x2) fy = midy;
        }

        res -= overlap(mida, midb, alpha1, alpha2);
    }
    res += interg(pi - alpha1, alpha1) - interg(0, alpha1) + 0.25 * sin(alpha1) * cos(alpha1); 
                                     // 推荐积分求解，不推荐写成 3*(pi-alpha)/16 + 1/16/tan(alpha) + (pi-alpha)/16/tan(alpha)/tan(alpha)
    return res;
}
int main(){
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%ld %ld", &dot[i].x, &dot[i].y);
    for (int i = 0; i < n; ++i)
        edge[i] = vec(dot[(i + 1) % n] - dot[i]);
    if (n == 4){                    // 特判4个点时的情况
        db len1 = edge[0].len(), len2 = edge[1].len(),
           len3 = edge[2].len(), len4 = edge[3].len();

        if (len1 == len3 and len2 == len4 and
            (len1 == 1 or len2 == 1) and
            fabs(angle(edge[0], edge[1]) - pi / 2.0) < eps)
            printf("%.11lf", len1 * len2), exit(0);
    }
    db res = 0.0;
    for (int i = 0; i < n; ++i)
        res += getarea((i - 1 + n) % n, i, (i + 1) % n);
    printf("%.11lf", res);
    return 0;
}

Python 3 的代码。

import math
pi = 3.14159265358979323846264338327950288419716939937510
eps, sq2 = 1e-6, pow(2, 0.5)
x, y, n = [], [], 0


def fabs(xx):
    return math.fabs(xx)


def Sin(xx):
    return math.sin(xx)


def Cos(xx):
    return math.cos(xx)


def Acos(xx):
    return math.acos(xx)


def get_len(ux, uy):
    return pow((pow(ux, 2) + pow(uy, 2)), 0.5)


def angel_(ux, uy, vx, vy, u, v):
    return Acos((ux * vx + uy * vy) / u / v)


def small(_a: float, _b: float) -> bool:
    return fabs(_a - _b) < eps


def big(_a: float, _b: float) -> bool:
    return fabs(_a - _b) > eps


def inter_grate(theta, alpha):
    ans = ((8 - 4 * Cos(2 * alpha)) * theta - 2 * Sin(4 * theta) + 4 * Sin(2 * theta + 2 * alpha)
           - Sin(6 * theta + 2 * alpha) + Sin(2 * alpha - 2 * theta)
           + Sin(4 * theta + 2 * alpha)) / (64 * pow(Sin(alpha), 2))
    return ans


def calc(la, ra, mid_y, alpha_1):
    while big(ra, la):
        mid_a = ra / 2.0 + la / 2.0
        yy = - pow(Sin(mid_a), 2) / Sin(alpha_1) * Cos(alpha_1 + mid_a)
        if yy > mid_y:
            la = mid_a
        if yy < mid_y:
            ra = mid_a
    return la, ra


def formulas_x(la, ra, alpha_1):
    return (2.0 * Sin(la / 2.0 + ra / 2.0 + alpha_1) + Sin(la + ra)
            * Cos(la / 2.0 + ra / 2.0 + alpha_1)) / (2 * Sin(alpha_1))


def binary_find(la, lb, ra, rb, cy, fy, alpha_1, alpha_2, ab):
    while big(cy, fy):
        mid_y = cy / 2.0 + fy / 2.0
        la, lb, ra, rb = 0.0, 0.0, pi - alpha_1, pi - alpha_2

        la, ra = calc(la, ra, mid_y, alpha_1)
        lb, rb = calc(lb, rb, mid_y, alpha_2)

        x1, x2 = formulas_x(la, ra, alpha_1), ab - formulas_x(lb, rb, alpha_2)

        if x1 < x2:
            cy = mid_y
        if x1 > x2:
            fy = mid_y
    return la, lb, ra, rb, cy, fy


def get_area(_i, ni, i_, i_2):
    ans = 0.00
    ux, uy, vx, vy = x[_i] - x[ni], y[_i] - y[ni], x[i_] - x[ni], y[i_] - y[ni]

    ab, ad = get_len(ux, vy), get_len(vx, uy)
    alpha_1 = angel_(ux, vy, vx, uy, ab, ad)

    if small(ab, sq2) or small(ab, 1.00):
        wx, wy = x[i_2] - x[i_], y[i_2] - y[i_]

        bc = get_len(wx, wy)
        alpha_2 = angel_(wx, wy, vx, vy, ab, bc)

        la, lb, ra, rb, cy, fy = 0.0, 0.0, pi - alpha_1, pi - alpha_2, Sin(min(alpha_1, alpha_2)), 0.0000
        la, lb, ra, rb, cy, fy = binary_find(la, lb, ra, rb, cy, fy, alpha_1, alpha_2, ab)

        ans -= inter_grate(la / 2.0 + ra / 2.0, alpha_1) - inter_grate(0, alpha_1)
        ans -= inter_grate(lb / 2.0 + rb / 2.0, alpha_2) - inter_grate(0, alpha_2)

    ans += inter_grate(pi - alpha_1, alpha_1) - inter_grate(0, alpha_1) + 0.5 * Sin(alpha_1) * Cos(alpha_1)
    return ans


if __name__ == "__main__":
    n = eval(input())
    for i in range(1, n + 1):
        a, b = input().split()
        a, b = int(eval(a)), int(eval(b))
        x.append(a), y.append(b)
    if n == 4:
        Ax, Ay, Bx, By, Cx, Cy, Dx, Dy = x[0], y[0], x[1], y[1], x[2], y[2], x[3], y[3]
        ABx, ABy, ADx, ADy = Bx - Ax, By - Ay, Dx - Ax, Dy - Ay
        CBx, CBy, CDx, CDy = Bx - Cx, By - Cy, Dx - Cx, Dy - Cy

        LenAB, LenAD, LenCB, LenCD = get_len(ABx, ABy), get_len(ADx, ADy), get_len(CBx, CBy), get_len(CDx, CDy)

        a, b = angel_(ABx, ABy, ADx, ADy, LenAB, LenAD), angel_(ABx, ABy, CBx, CBy, LenAB, LenCB)
        c, d = angel_(CDx, CDy, CBx, CBy, LenCD, LenCB), angel_(CDx, CDy, ADx, ADy, LenCD, LenAD)

        if small(a, pi / 2.0) and small(b, pi / 2.0) and small(c, pi / 2.0) and small(d, pi / 2.0) and \
         ((small(LenAB, 1.00) and small(LenAB, LenCD)) or (small(LenCB, 1.00) and small(LenCB, LenAD))):
            print('%.11Lf' % (LenAB * LenCB)), exit(0)

    res = 0.0000
    for i in range(1, n + 1):
        res += get_area((i - 1 + n) % n, i % n, (i + 1) % n, (i + 2) % n)

    print('%.11Lf' % res)

问题拓展

如果完全抛开凸多边形的鬼畜计算和直角钝角的性质不谈，只考虑单个锐角不取到 $0^\circ,180^\circ$ 以外的情况，又会是个什么情况？

首先可以想象出下面的样子。

可观察到杆 $AC$ 位于 $x$ 轴的端点一直从点 $C$ 运动到点 $G$ 后收回到 $F$。而另一个端点则是先上升到点 $D$ 后一直沿着夹角 $\alpha$ 的一边往 $C$ 走。

同时也不难想象围成图形的面积由两部分构成，即三角形面积加上包络线的积分值。也即 $\dfrac{1}{2\tan\alpha}+\displaystyle \int y\mathrm{d}x$。

而包络线的计算方式可以继续沿用之前的思想。

假如让 $\angle \text{DEC}$ 作为 $\theta$，那么包络线上的点 $(x,y)$ 必定经过直线 $l:y=-\tan\theta(x-x_0)$，且存在关系

$$\begin{aligned}&\dfrac{x_0}{\sin(\pi-\alpha-\theta)} = \dfrac{1}{\sin\alpha}\Rightarrow x_0 = \dfrac{\sin(\alpha+\theta)}{\sin\alpha} \\
&\dfrac{\mathrm d y}{\mathrm d x} = \dfrac{y_\theta}{x_\theta} = -\tan\theta\Rightarrow y_\theta = -\tan\theta x_\theta\end{aligned}$$

变形整理得到
$$\begin{cases}x = \dfrac{2\sin(\alpha + \theta) + \sin2\theta\cos(\alpha + \theta)}{2\sin\alpha} \\ y = -\dfrac{\sin^2\theta\cos(\alpha + \theta)}{2\sin\alpha} \end{cases}$$

结果是完全一致的。我们再来考虑积分的上下限。

由图片不难看到，最开始的下限是 $\dfrac{\pi}{2}$，上限是 $\dfrac{\pi}{2}-\alpha$。在经过上文的积分后即可，无需减掉三角形面积，保留即可得到正确答案。

所以，对于单个锐角而言，其覆盖的面积为

$$\begin{aligned}\text{S}(\alpha) &= \dfrac{1}{2\tan\alpha} + \Big(\left. \dfrac{1}{64\sin^2\alpha}
[
(8-4\cos2\alpha)\theta-2\sin4\theta+4\sin(2\theta+2\alpha)
-\sin(6\theta+2\alpha)
+\sin(2\alpha-2\theta)
+\sin(4\theta+2\alpha)]
\right|_{\frac{\pi}{2} - \alpha}^{\frac{\pi}{2}}\Big).
\end{aligned}$$

参考网页与在线工具

1. https://bilibili.com/video/av370957522

2. https://www.bilibili.com/video/BV13s4y1X7yb

3. https://codeforces.com/blog/entry/106675

4. https://www.wolframalpha.com/

5. https://www.latexlive.com/

6. https://www.geogebra.org/calculator

最后，欢迎纠错。