牛客多校第四场 B 题题解

B 2D Internet Angel

B 题题意：给定内外同心圆，半径分别为 $R_1,R_{2}R\_1,R\_2$，沿内侧圆外有一 $nn$ 边外接多边形 $\{P_i\}\backslash \{P\_i\backslash \}$，与内侧圆的切点为 $\{Q_i\}\backslash \{Q\_i\backslash \}$，保证这一多边形完全在外侧圆内。记此外接多边形外与外侧圆内侧部分的点到多边形和内侧圆切点的最近距离为 $XX$，求 $E(X^2)E(X^2)$。$n\le 1\times 10^{5}n\; \backslash leq\; 1\backslash times\; 10^5$。

解法：过凸包顶点 $P_i(x_i,y_i)P\_i(x\_i,y\_i)$ 和 $P_{i+1}(x_{i+1},y_{i+1})P\_\{i+1\}(x\_\{i+1\},y\_\{i+1\})$ 的中点 $Q_{i}Q\_\{i\}$，和外侧圆弧（即 $F{P}_2{Q}_{2}EFP\_2Q\_2E$）所包络区域内的点的最近距离是到 $Q_{i}Q\_i$ 点的距离。记 $P_{i}P\_i$ 极角为 ${\beta }_i\backslash beta\_i$，$Q_{i}Q\_i$ 极角为 ${\alpha }_i\backslash alpha\_i$，设一点位于 $U(x,y)U(x,y)$，则利用 $\mathrm{\Delta }UOQ\backslash Delta\; UOQ$ 的余弦定理，设 $\mathrm{\angle }{P}_{i}OU=\theta \backslash angle\; P\_iOU=\backslash theta$，$\mathrm{\angle }UO{Q}_i={\alpha }_i-{\beta }_i-\theta \backslash angle\; UOQ\_i=\backslash alpha\_i-\backslash beta\_i-\backslash theta$，则有 $U{Q}_2^2=O{U}^2+O{Q}_2^2-2OU\cdot O{Q}_2\cos ({\alpha }_i-{\beta }_i-\theta )UQ\_2^2=OU^2+OQ\_2^2-2OU\backslash cdot\; OQ\_2\; \backslash cos(\backslash alpha\_i-\backslash beta\_i-\backslash theta)$，因而只与 $OU=rOU=r$ 和极角 $\theta \backslash theta$ 有关，因而可以利用极坐标下二重积分，计算出对于 $Q_{i}Q\_i$ 答案为：

二倍的原因在于 $\mathrm{\angle }{P}_{i}O{Q}_i=\mathrm{\angle }{Q}_{i}O{P}_{i+1}\backslash angle\; P\_iOQ\_i=\backslash angle\; Q\_iOP\_\{i+1\}$。

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

因而可以 $\mathcal{O}(1)\backslash mathcal\; O(1)$ 的计算出每个 $Q_{i}Q\_i$ 的答案。最后只需要使用直线与直线的交算出 $P_{i}P\_i$，得到凸多边形 $C=\{P_n\}C=\backslash \{P\_n\backslash \}$ 然后求出其面积 $SS$，答案为 ${\displaystyle \frac{\sum _{i=1}^n{g}_i}{\pi R_2^2-S_C}}\backslash displaystyle\; \backslash dfrac\{\backslash sum\_\{i=1\}^n\; g\_i\}\{\backslash 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;
}