牛客多校第二场 B 题题解

B Light

B 题题意：给定一个凸多边形 $\{C_n\}\backslash \{C\_n\backslash \}$，在这一多边形向内延申 $ww$ 的范围有一堵高为 $hh$ 的墙，墙内多边形记为 $C^{\mathrm{\prime }}C\text{'}$。现在在点 $L(x,y,z)L(x,y,z)$ 处有一点光源，问该点光源照射到 $C^{\mathrm{\prime }}C\text{'}$ 的面积。$n\le 2\times 10^{3}n\; \backslash leq\; 2\backslash times\; 10^3$。

解法：对于凸多边形，向内缩 $ww$ 可以使用半平面交：对于每条原多边形的边 $(P,\vec{v})(P,\backslash vec\{v\})$，向内缩 $ww$ 即是一个半平面 $(P+{\displaystyle \frac{w}{\mathrm{\mid }\overrightarrow{v^{\mathrm{\prime }}}\mathrm{\mid }}}\overrightarrow{v^{\mathrm{\prime }}},\vec{v})\backslash left(P+\backslash dfrac\{w\}\{|\backslash vec\{v\text{'}\}|\}\backslash vec\{v\text{'}\},\backslash vec\{v\}\backslash right)$，其中 $\overrightarrow{v^{\mathrm{\prime }}}\backslash vec\{v\text{'}\}$ 表示 $\vec{v}\backslash vec\{v\}$ 沿逆时针方向旋转 ${\displaystyle \frac{\pi }{2}}\backslash dfrac\{\backslash pi\}\{2\}$ 所得向量。

对于点光源照射部分，对于每堵墙的限制，只需要判断 $LL$ 是在该墙 $(P,\vec{v})(P,\backslash vec\{v\})$ 的左侧还是右侧。若为左侧，则墙无法阻拦光线；否则墙就会有阻挡作用。只有当 $z>hz>h$ 时才会有光射入该半平面，延申长度可以使用相似三角形求出——该操作就是继续对该内缩的凸多边形继续内缩，只是这次内缩距离是由点光源到墙的距离给出的。

因而使用半平面交即可轻松求出面积。总复杂度 $\mathcal{O}(n^2)\backslash mathcal\; O(n^2)$。

只放上主函数：

int main()
{
    int t, n;
    double h, x, y, z, w;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%lf%lf", &n, &h, &w);
        auto nx = [&](int x)
        {
            return (x + 1) % n;
        };
        vector<Point> que(n);
        for (int i = 0; i < n;i++)
            scanf("%lf%lf", &que[i].x, &que[i].y);
        scanf("%lf%lf%lf", &x, &y, &z);
        Convex out = convexhull(que);
        vector<Line> shrink(n);
        for (int i = 0; i < n;i++)
        {
            shrink[i].v = out.p[nx(i)] - out.p[i];
            auto dir = out.p[nx(i)] - out.p[i];
            auto verdir = (Point){-dir.y, dir.x};
            shrink[i].p = out.p[i] + verdir * (w / verdir.len());
        }
        auto inner = halfinter(shrink);
        if (inner.size() <= 2)
        {
            printf("0\n");
            continue;
        }
        auto newinner = inner;
        Point light = (Point){x, y};
        bool flag = 0;
        auto ori = halfint_to_convex(inner);
        double outer = ori.area();
        for (auto i : inner)
        {
            auto res = i.toleft(light);
            if (res == -1)
            {
                if (z <= h)
                {
                    flag = 1;
                    break;
                }
                double light_to_wall = i.dis(light);
                double verdis = light_to_wall * h / (z - h);
                Point verdir = (Point){-i.v.y, i.v.x};
                Line nowline;
                nowline.v.x = i.v.x;
                nowline.v.y = i.v.y;
                nowline.p = i.p + verdir * (verdis / verdir.len());
                newinner.push_back(nowline);
            }
        }
        if(flag)
        {
            printf("0\n");
            continue;
        }
        auto ans = halfinter(newinner);
        auto shade = halfint_to_convex(ans).area();
        printf("%.10lf\n", shade);
    }
    return 0;
}