牛客多校第四场 B 题题解

B 2D Internet Angel

B 题题意：给定内外同心圆，半径分别为 $R_{1}, R_{2}$ ，沿内侧圆外有一 $n$ 边外接多边形 ${P_{i}}$ ，与内侧圆的切点为 ${Q_{i}}$ ，保证这一多边形完全在外侧圆内。记此外接多边形外与外侧圆内侧部分的点到多边形和内侧圆切点的最近距离为 $X$ ，求 $E (X^{2})$ 。 $n \leq 1\times 10^5$ 。

解法：过凸包顶点 $P_{i} (x_{i}, y_{i})$ 和 $P_{i+1}(x_{i+1},y_{i+1})$ 的中点 $Q_{i}$ ，和外侧圆弧（即 $F P_{2} Q_{2} E$ ）所包络区域内的点的最近距离是到 $Q_{i}$ 点的距离。记 $P_{i}$ 极角为 $\beta_i$ ， $Q_{i}$ 极角为 $\alpha_i$ ，设一点位于 $U (x, y)$ ，则利用 $\Delta UOQ$ 的余弦定理，设 $\angle P_iOU=\theta$ ， $\angle UOQ_i=\alpha_i-\beta_i-\theta$ ，则有 $UQ_2^2=OU^2+OQ_2^2-2OU\cdot OQ_2 \cos(\alpha_i-\beta_i-\theta)$ ，因而只与 $O U = r$ 和极角 $\theta$ 有关，因而可以利用极坐标下二重积分，计算出对于 $Q_{i}$ 答案为：

g_i=2\int_{0}^{\alpha_i-\beta_i} {\rm d}\theta\int_{R_1\sec (\alpha_i-\beta_i-\theta)}^{R_2} (R_1^2+r^2-2R_1r\cos (\alpha_i-\beta_i-\theta))r{\rm d}r

alt

二倍的原因在于 $\angle P_iOQ_i=\angle Q_iOP_{i+1}$ 。

考虑计算如下的二重积分：

\begin{aligned} f(\alpha)=&\int_{0}^{\alpha}{\rm d}\theta\int_{R_1\sec\theta}^{R_2} (R_1^2+r^2-2R_1r\cos \theta)r{\rm d}r\\ =&\int_{0}^{\alpha}{\rm d}\theta \left .\left(\dfrac{R_1^2r^2}{2}+\dfrac{1}{4}r^4-\dfrac{2R_1r^3}{3}\cos \theta\right)\right |_{R_1\sec \theta}^{R_2}\\ =&\alpha\left(\dfrac{R_1^2R_2^2}{2}+\dfrac{1}{4}R_2^4\right)-\dfrac{R_1^4}{4}\int_{0}^{\alpha}2\sec^2 \theta+\sec^4 \theta{\rm d}\theta-\dfrac{2R_1R_2^3}{3}\int_{0}^{\alpha}\cos \theta{\rm d}\theta+\dfrac{2R_1^4}{3}\int_{0}^{\alpha}\sec^2 \theta{\rm d}\theta\\ =&\alpha\left(\dfrac{R_1^2R_2^2}{2}+\dfrac{1}{4}R_2^4\right)-\dfrac{R_1^4\tan \alpha}{12\cos^ 2\alpha}-\dfrac{2}{3}R_1R_2^3\sin \alpha \end{aligned}

因而可以 $\mathcal O(1)$ 的计算出每个 $Q_{i}$ 的答案。最后只需要使用直线与直线的交算出 $P_{i}$ ，得到凸多边形 $C=\{P_n\}$ 然后求出其面积 $S$ ，答案为 $\displaystyle \dfrac{\sum_{i=1}^n g_i}{\pi R_2^2-S_C}$ 。

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int n;
        scanf("%d%Lf%Lf", &n, &r1, &r2);
        vector<Point> Q(n), P(n);
        vector<int> angQ(n);
        for (int i = 0, x; i < n;i++)
        {
            scanf("%d", &x);
            angQ[i] = x;
            Q[i].x = r1 * cosl(x * PI / 10000);
            Q[i].y = r1 * sinl(x * PI / 10000);
        }
        for (int i = 0; i < n;i++)
        {
            Line now;
            now.p = Q[i];
            now.v = (Point){-Q[i].y, Q[i].x};
            Line nx;
            nx.p = Q[(i + 1) % n];
            nx.v = (Point){-Q[(i + 1) % n].y, Q[(i + 1) % n].x};
            P[i] = nx.inter(now);
        }
        auto inner = convexhull(P);
        auto cal_ang = [&](int id)
        {
            return atan2l(P[id].y, P[id].x);
        };
        long double ans = 0;
        for (int i = 0; i < n;i++)
        {
            long double nowQ = angQ[i] * PI / 10000;
            long double prevP = cal_ang((i + n - 1) % n);
            long double nowP = cal_ang(i);
            while(prevP > nowQ)
                prevP -= PI;
            while(nowP < nowQ)
                nowP += PI;
            ans += f(nowP - nowQ) + f(nowQ - prevP);
        }
        printf("%.15Lf\n", ans / (r2 * r2 * PI - inner.area() / 2));
    }
    return 0;
}