✅ 题解：寻找凸多边形的内切圆半径（距离边界最远点的距离）

🔍 问题转化

题目要求我们找一个 凸多边形内部到边界最远的点，这个点显然是该多边形内切圆的圆心，该最远距离就是内切圆的半径。

💡 解题思路

1. 观察问题：

   • 目标是在给定的凸多边形内找一个点，使它到所有边的最短距离最大。
   • 本质上就是在该多边形内，找能放下最大的圆（即内切圆），其圆心是目标点，半径是要求的最大最小距离。

2. 二分查找半径：

   • 二分猜测一个半径 $r$，尝试在原多边形中构造一个缩小$r$单位的多边形。
   • 如果这个“缩小多边形”非空，说明存在某个点到边界距离大于$r$；否则$r$太大了。

3. 半平面交判断是否非空：

   • 将多边形的每条边沿法向量方向平移$r$单位，形成一个新的半平面。
   • 将所有半平面做半平面交，若结果非空，则该$r$是合法的，可以尝试更大。
   • 最终的最大$r$就是答案。

🧠 关键算法：半平面交

半平面交是将多个半平面（直线及其一侧）求公共部分，通常用于计算多边形交集。

📌 解题步骤

1. 输入多边形顶点，构造每条边的向量。
2. 通过该向量求出单位法向量。
3. 二分半径$r$，对于每条边平移$r$并构造半平面。
4. 使用半平面交算法判断是否存在交集（即存在满足条件的点）。
5. 输出最大的合法$r$，即为所求答案。

✅ 完整代码（C++）

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const double eps = 1e-8;
const int maxn = 210;

struct Point {
    double x, y;
    Point(double x = 0, double y = 0): x(x), y(y) {}
};

typedef Point Vector;

Vector operator + (Vector a, Vector b) { return Vector(a.x + b.x, a.y + b.y); }
Vector operator - (Vector a, Vector b) { return Vector(a.x - b.x, a.y - b.y); }
Vector operator * (Vector a, double p) { return Vector(a.x * p, a.y * p); }
Vector operator / (Vector a, double p) { return Vector(a.x / p, a.y / p); }

double Cross(Vector a, Vector b) { return a.x * b.y - a.y * b.x; }
double Dot(Vector a, Vector b) { return a.x * b.x + a.y * b.y; }
double Length(Vector a) { return sqrt(Dot(a, a)); }

Point Verunit(Point a) {
    return Point(-a.y, a.x) / Length(a); // 垂直单位向量
}

struct Line {
    Point p;
    Vector v;
    double ang;
    Line() {}
    Line(Point p, Vector v): p(p), v(v) {
        ang = atan2(v.y, v.x);
    }
    bool operator < (const Line& b) const {
        return ang < b.ang;
    }
};

bool OnLeft(Line L, Point p) {
    return Cross(L.v, p - L.p) > eps;
}

Point GetIntersection(Line a, Line b) {
    Vector u = a.p - b.p;
    double denom = Cross(a.v, b.v);
    if (fabs(denom) < eps) return Point(1e20, 1e20); // 平行
    double t = Cross(b.v, u) / denom;
    return a.p + a.v * t;
}

int HalfplaneIntersection(Line *L, int n, Point *poly) {
    sort(L, L + n);
    static Line q[maxn];
    static Point p[maxn];
    int first = 0, last = 0;
    q[0] = L[0];
    for (int i = 1; i < n; i++) {
        while (first < last && !OnLeft(L[i], p[last - 1])) last--;
        while (first < last && !OnLeft(L[i], p[first])) first++;
        q[++last] = L[i];
        if (fabs(Cross(q[last].v, q[last - 1].v)) < eps) {
            last--;
            if (OnLeft(q[last], L[i].p)) q[last] = L[i];
        }
        if (first < last) p[last - 1] = GetIntersection(q[last - 1], q[last]);
    }
    while (first < last && !OnLeft(q[first], p[last - 1])) last--;
    if (last - first <= 1) return 0;
    p[last] = GetIntersection(q[last], q[first]);
    int m = 0;
    for (int i = first; i <= last; i++) poly[m++] = p[i];
    return m;
}

int main() {
    int n;
    Point p[maxn], poly[maxn];
    Line L[maxn];
    Vector v[maxn], v2[maxn];

    while (scanf("%d", &n) == 1 && n != 0) {
        for (int i = 0; i < n; i++) scanf("%lf %lf", &p[i].x, &p[i].y);

        // ✅ 检查面积是否为0（退化情况，输出0.000000）
        double area = 0.0;
        for (int i = 0; i < n; i++) {
            area += Cross(p[i], p[(i + 1) % n]);
        }
        area = fabs(area) / 2.0;
        if (area < eps) {
            printf("0.000000\n");
            continue;
        }

        // 构造每条边及其单位法向量
        for (int i = 0; i < n; i++) {
            v[i] = p[(i + 1) % n] - p[i];    // 边向量
            v2[i] = Verunit(v[i]);           // 单位法向量
        }

        double left = 0, right = 10050; // 二分查找的初始范围
        while (right - left > eps) {
            double mid = (left + right) / 2;
            for (int i = 0; i < n; i++) {
                L[i] = Line(p[i] + v2[i] * mid, v[i]); // 向内平移
            }
            int m = HalfplaneIntersection(L, n, poly);
            if (m == 0) right = mid;       // 没有合法区域，缩小半径
            else left = mid;               // 存在合法区域，扩大半径
        }

        printf("%.6lf\n", left);
    }

    return 0;
}

🧪 示例运行

输入：

4
0 0
10000 0
10000 10000
0 10000
0

输出：

5000.000000

表示在这个正方形内，最远点距离边界为5000（正中心）。

✅ 总结

• 本题关键在于将“最远距离问题”转化为“内切圆最大半径问题”。
• 通过二分半径 + 半平面交方法高效求解。
• 适用于任意凸多边形，满足题目条件。