UVa 11177 Fighting against a Polygonal Monster

本文提出了一种求解以原点为圆心的圆与凸多边形相交面积的最小半径的算法。通过二分搜索确定满足相交面积≥R的最小半径，每次迭代中计算多边形每条边与圆的相交面积并累加。利用几何性质将多边形分解为三角形，分别处理完全在圆内、完全在圆外及与圆相交的情况。算法复杂度为O(n log(精度^-1))，适用于顶点数≤50的多边形。示例输入输出验证了算法的正确性。

寂静山林

773人浏览 · 2026-02-13 08:10:39

寂静山林 · 2026-02-13 08:10:39 发布

题目描述

你正在对抗一个多边形怪物。你有一件特殊武器，可以发射激光束。激光束可以看作是沿着 $z$ 轴的圆柱体，因此从 $X Y$ 平面上方看，激光束实际上是一个以 $(0, 0)$ 为中心的圆（你无法改变圆心位置）。怪物是一个凸多边形（你可以把它想象成一个非常薄的棱柱），它有 $n$ 个顶点，并且原点 $(0, 0)$ 严格位于怪物内部（不在边界上）。

已知当激光束与怪物的公共面积至少为 $R$ 时，怪物死亡。由于激光束越大消耗的能量越多，你希望找到激光束的最小半径。

编写程序计算最小半径。保证 $\leq R \leq A)$ ，其中 $A$ 是怪物的面积。

输入格式

最多 $10$ 组测试数据。每组数据以一个整数 $n$ （ $\leq n \leq 50$ ）和一个浮点数 $R$ 开始，接下来 $n$ 行每行两个实数，表示怪物的顶点坐标。顶点按逆时针或顺时针顺序给出。最后一组数据后是一个单独的 $0$ ，表示输入结束。

输出格式

对于每组数据，输出案例编号和最小半径，保留两位小数。输入保证即使使用双精度浮点数，微小的精度误差也不会影响可见输出。

示例输入

示例输出

Case 1: 0.93

题目分析

本题的核心是计算以原点为圆心的圆与给定凸多边形的相交面积，并找到使得该面积至少为 $R$ 的最小半径 $r$ 。

关键性质

圆心固定：激光束的圆心始终在原点 $(0, 0)$ 。
多边形包含原点：原点严格位于多边形内部，这意味着对于任何半径 $r$ ，圆与多边形的相交区域都是连续的。
凸多边形：多边形的凸性简化了几何计算。
单调性：半径 $r$ 越大，相交面积越大，因此可以通过二分搜索求解。

解题思路

1. 二分搜索框架

由于相交面积 $S (r)$ 是 $r$ 的单调递增函数，我们可以使用二分搜索来找到满足 $\geq R$ 的最小 $r$ 。

搜索范围：从 $0$ 到足够大的值（如 $10^5$ ）。
迭代次数：进行固定次数的二分迭代（如 $60$ 次），以获得足够的精度。
判断条件：计算当前半径 $mi d$ 下的相交面积，若 $≥R\geq R$ 则缩小右边界，否则增大左边界。

2. 计算相交面积

对于凸多边形与圆的相交面积，我们可以将多边形分解为以原点为顶点的三角形，分别计算每个三角形与圆的相交面积，然后求和。

对于三角形 $△OAB\triangle OAB$ （其中 $O$ 为原点， $A$ 和 $B$ 为多边形相邻顶点），其与半径为 $r$ 的圆的相交面积可以通过以下情况计算：

情况 1： $A$ 和 $B$ 都在圆内

此时三角形完全在圆内，相交面积就是三角形 $△OAB\triangle OAB$ 的面积：

$S_{\triangle OAB} = \frac{1}{2} |\vec{OA} \times \vec{OB}|$

情况 2： $A$ 和 $B$ 都在圆外，且线段 $A B$ 与圆无交点

此时三角形与圆的相交部分是一个扇形，其圆心角为 $∠AOB\angle AOB$ ，面积为：

$S_{\text{sector}} = \frac{1}{2} \theta r^2$

其中 $θ\theta$ 为向量 $OA⃗\vec{OA}$ 与 $OB⃗\vec{OB}$ 的夹角（ $\sim 2\pi$ ）。

情况 3： $A$ 在圆内， $B$ 在圆外（或反之）

设线段 $A B$ 与圆的交点为 $P$ （靠近 $B$ 侧）。则相交面积由两部分组成：

三角形 $△OAP\triangle OAP$ 的面积（完全在圆内）。
扇形 $∠POB\angle POB$ 的面积。

情况 4： $A$ 和 $B$ 都在圆外，且线段 $A B$ 与圆有两个交点 $P_1$ 和 $P_2$

此时相交面积由三部分组成：

扇形 $∠AOP1\angle AOP_1$ 的面积。
三角形 $△OP1P2\triangle OP_1P_2$ 的面积。
扇形 $∠P2OB\angle P_2OB$ 的面积。

3. 几何计算细节

线段与圆的交点：通过求解直线参数方程与圆的方程得到交点，再判断交点是否在线段上。
向量夹角：使用 $atan2\text{atan2}$ 函数计算夹角，并调整到 $2\pi)$ 范围。
方向处理：确保多边形顶点顺序为逆时针，以保证面积计算为正。

算法步骤

读入多边形顶点，确保其为逆时针顺序。
二分搜索半径 $r$ ：
- 对于每个候选半径 $mi d$ ，调用函数计算圆与多边形的相交面积。
- 相交面积计算：遍历多边形的每条边，计算对应的三角形 $△OAB\triangle OAB$ 与圆的相交面积，累加得到总面积。
- 根据总面积与 $R$ 的比较调整搜索边界。
输出结果，保留两位小数。

时间复杂度

每个测试案例：二分搜索 $O(log⁡(O(\log($ 精度 $^{-1}))$ 次，每次计算相交面积需要 $O (n)$ 时间，其中 $n$ 为顶点数。
总体复杂度： $\log($ 精度 $^{-1}))$ ，对于 $\leq 50$ 和 $60$ 次二分迭代，完全可行。

代码实现

// Fighting against a Polygonal Monster
// UVa ID: 11177
// Verdict: Accepted
// Submission Date: 2026-01-14
// UVa Run Time: 0.000s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>
using namespace std;

const double PI = acos(-1.0);
const double EPS = 1e-9;

int dcmp(double x) { return fabs(x) < EPS ? 0 : (x < 0 ? -1 : 1); }

struct Point {
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}
    Point operator - (const Point &p) const { return Point(x - p.x, y - p.y); }
    Point operator + (const Point &p) const { return Point(x + p.x, y + p.y); }
    Point operator * (double d) const { return Point(x * d, y * d); }
    double operator * (const Point &p) const { return x * p.y - y * p.x; } // 叉积
    double dot(const Point &p) const { return x * p.x + y * p.y; }
    double len() const { return sqrt(x * x + y * y); }
    double len2() const { return x * x + y * y; }
};

// 向量夹角（0 ~ 2π）
double angleBetween(Point a, Point b) {
    double dot = a.dot(b);
    double det = a * b;
    double ang = atan2(det, dot);
    if (ang < 0) ang += 2 * PI;
    return ang;
}

// 扇形面积：圆心角 theta，半径 r
double sectorArea(double theta, double r) {
    return 0.5 * theta * r * r;
}

// 三角形 OAB 的有向面积
double triangleArea(Point a, Point b) {
    return fabs(a * b) / 2.0;
}

// 计算三角形 OAB 与半径为 r 的圆的相交面积
double triangleCircleIntersection(Point a, Point b, double r) {
    double da = a.len(), db = b.len();
    // 两个点都在圆内
    if (dcmp(da - r) <= 0 && dcmp(db - r) <= 0) return triangleArea(a, b);
    // 两个点都在圆外且线段与圆无交点
    Point d = b - a;
    double A = d.dot(d);
    double B = 2 * d.dot(a);
    double C = a.dot(a) - r * r;
    double delta = B * B - 4 * A * C;
    if (dcmp(delta) <= 0) {
        double theta = angleBetween(a, b);
        return sectorArea(theta, r);
    }
    double t1 = (-B - sqrt(delta)) / (2 * A);
    double t2 = (-B + sqrt(delta)) / (2 * A);
    if (t2 < 0 || t1 > 1) {
        double theta = angleBetween(a, b);
        return sectorArea(theta, r);
    }
    t1 = max(t1, 0.0);
    t2 = min(t2, 1.0);
    Point p1 = a + d * t1;
    Point p2 = a + d * t2;
    double res = 0;
    // A -> p1
    if (dcmp(da - r) <= 0) {
        res += triangleArea(a, p1);
    } else {
        double theta = angleBetween(a, p1);
        res += sectorArea(theta, r);
    }
    // p1 -> p2
    res += triangleArea(p1, p2);
    // p2 -> B
    if (dcmp(db - r) <= 0) {
        res += triangleArea(p2, b);
    } else {
        double theta = angleBetween(p2, b);
        res += sectorArea(theta, r);
    }
    return res;
}

// 计算圆与多边形的相交面积
double areaCirclePolygon(const vector<Point> &poly, double r) {
    double area = 0;
    int n = poly.size();
    for (int i = 0; i < n; i++) {
        Point a = poly[i], b = poly[(i + 1) % n];
        area += triangleCircleIntersection(a, b, r);
    }
    return area;
}

int main() {
    int n, caseNo = 1;
    double R;
    while (cin >> n && n) {
        cin >> R;
        vector<Point> poly(n);
        for (int i = 0; i < n; i++) cin >> poly[i].x >> poly[i].y;
        // 确保多边形面积为正（逆时针）
        double polyArea = 0;
        for (int i = 0; i < n; i++) polyArea += poly[i] * poly[(i + 1) % n];
        if (dcmp(polyArea) < 0) reverse(poly.begin(), poly.end());
        // 二分搜索半径
        double left = 0, right = 1e5;
        for (int iter = 0; iter < 60; iter++) {
            double mid = (left + right) / 2;
            double interArea = areaCirclePolygon(poly, mid);
            if (interArea >= R) right = mid;
            else left = mid;
        }
        cout << fixed << setprecision(2) << "Case " << caseNo++ << ": " << left << endl;
    }
    return 0;
}