题意分析

题目描述了一个副热带太平洋上的浮空岛国家，其首都拉普克斯是一个半径为$R_0$的圆形浮空岛。每年夏至正午时，拉普克斯会沿着一个多边形路径移动，并在正下方投下阴影。阴影会被周围的云环放大，半径在路径的每一段必须保持不变，仅在顶点处可调整。阴影半径需要满足以下条件：

1. 阴影不得覆盖任何岛屿；
2. 阴影半径在路径的每一段必须保持不变，仅在顶点处可调整；
3. 阴影半径应尽可能大，但不得超过技术上限$R_1$；
4. 如果某段路径的阴影半径无法满足不小于$R_0$，则该段路径不可行，输出$0$。

输入包括：

• $R_0$和$R_1$：浮空岛的半径和技术上限；
• $n$：岛屿的数量；
• 每个岛屿的顶点坐标（凸多边形）；
• 路径的顶点坐标（折线）。

输出为路径每一段的阴影半径（四舍五入取整），若某段不可行则输出$0$。

解题思路

问题分解

我们需要为路径的每一段计算一个最大的阴影半径$r$，使得：

1. $R_0 \leq r \leq R_1$；
2. 路径的整条线段与所有岛屿的最小距离至少为$r$；
3. 如果无法满足$r \geq R_0$，则该段路径不可行，输出$0$。

关键步骤

1. 计算线段与凸多边形的最小距离：

   • 对于路径的每一段线段，我们需要计算它与所有岛屿的最小距离。这个最小距离就是该线段可以使用的最大阴影半径$r$。
   • 线段与凸多边形的最小距离可以分解为线段与多边形每条边的最小距离，以及线段端点到多边形的距离的最小值。

2. 计算线段与线段的最小距离：

   • 对于线段$AB$和多边形的边$CD$，计算$AB$与$CD$的最短距离。如果两线段相交，则距离为$0$。
   • 否则，最短距离是$A$到$CD$、$B$到$CD$、$C$到$AB$、$D$到$AB$的最小距离。

3. 计算点到多边形的最小距离：

   • 对于路径的端点，计算它到所有岛屿的最小距离。这个距离是点到多边形每条边的最短距离。

4. 确定每段路径的最大$r$：

   • 对于路径的每一段线段，计算它与所有岛屿的最小距离$d$。
   • 该段路径的最大$r$为$\min(d, R_1)$。
   • 如果$r < R_0$，则该段路径不可行，输出$0$；否则输出$r$（四舍五入取整）。

算法选择

• 对于每段路径线段，遍历所有岛屿的边，计算线段与边的最小距离。
• 同时计算路径线段端点到所有岛屿的最小距离。
• 取所有这些距离的最小值作为该段路径的最大允许$r$。
• 最后根据$R_0$和$R_1$调整$r$的值。

标程

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
using namespace std;

// 点的结构体
struct Point {
    double x, y;
    Point(double _x = 0, double _y = 0) : x(_x), y(_y) {}
};

// 计算两点间距离
double dist(Point p1, Point p2) {
    return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}

// 计算点到线段的距离
double pointToSegmentDist(Point p, Point a, Point b) {
    double abLen = dist(a, b);
    if (abLen < 1e-9) return dist(p, a); // 线段退化为点
    
    double t = ((p.x - a.x) * (b.x - a.x) + (p.y - a.y) * (b.y - a.y)) / (abLen * abLen);
    if (t < 0) return dist(p, a);
    if (t > 1) return dist(p, b);
    
    Point projection(
        a.x + t * (b.x - a.x),
        a.y + t * (b.y - a.y)
    );
    return dist(p, projection);
}

// 计算线段到线段的最短距离
double segmentToSegmentDist(Point a1, Point a2, Point b1, Point b2) {
    double d1 = pointToSegmentDist(a1, b1, b2);
    double d2 = pointToSegmentDist(a2, b1, b2);
    double d3 = pointToSegmentDist(b1, a1, a2);
    double d4 = pointToSegmentDist(b2, a1, a2);
    return min(min(d1, d2), min(d3, d4));
}

// 计算线段到多边形的最短距离
double segmentToPolygonDist(Point s, Point e, const vector<Point>& poly) {
    double minDist = 1e18; // 初始化为很大的值
    
    // 检查线段到多边形每条边的距离
    for (size_t i = 0; i < poly.size(); ++i) {
        size_t j = (i + 1) % poly.size();
        minDist = min(minDist, segmentToSegmentDist(s, e, poly[i], poly[j]));
    }
    
    return minDist;
}

int main() {
    double R0, R1;
    int n;
    while (cin >> R0 >> R1 >> n && (R0 != 0 || R1 != 0 || n != 0)) {
        vector<vector<Point> > islands(n);
        for (int i = 0; i < n; ++i) {
            int ni;
            cin >> ni;
            islands[i].resize(ni);
            for (int j = 0; j < ni; ++j) {
                cin >> islands[i][j].x >> islands[i][j].y;
            }
        }
        int m;
        cin >> m;
        vector<Point> path(m);
        for (int i = 0; i < m; ++i) {
            cin >> path[i].x >> path[i].y;
        }
        vector<int> radii(m - 1);
        for (int i = 0; i < m - 1; ++i) {
            double minDist = R1;
            for (int j = 0; j < n; ++j) {
                minDist = min(minDist, segmentToPolygonDist(path[i], path[i + 1], islands[j]));
            }
            if (minDist < R0 - 1e-9) { // 考虑浮点数精度
                radii[i] = 0;
            } else if (minDist >= R1 - 1e-9) {
                radii[i] = static_cast<int>(R1 + 0.5);
            } else {
                radii[i] = static_cast<int>(minDist + 0.5);
            }
        }
        for (size_t i = 0; i < radii.size(); ++i) {
            cout << radii[i];
            if (i < radii.size() - 1) cout << " ";
        }
        cout << endl;
    }
    return 0;
}