题意简述

给定一个简单多边形（逆时针给出顶点），求能完全放在多边形内部的最长线段的长度。

关键观察

最长线段性质 这样的最长线段一定满足：

两个端点都在多边形的边界上，或者

至少有一个端点是多边形的顶点（实际上，可以证明两个端点都在多边形顶点上）。

事实上，这是一个已知结论：多边形内最长线段一定是某两个顶点之间的连线（如果整条线段在多边形内部）。

证明思路

如果线段的一个端点不在顶点上，我们可以沿多边形边界滑动它，直到碰到顶点，这样线段长度不会减少。

问题转化

我们需要检查所有顶点对 $(A, B)$，判断线段 $AB$ 是否完全在多边形内部，然后取最大值。

如何判断线段是否在多边形内部

对于线段 $AB$：

端点在内部分 两个端点 $A,B$ 必须在多边形内部或边界上（由于是简单多边形，在线段上的点算作内部）。

不与任何非相邻边相交 线段 $AB$ 不能与多边形的任何边（除了可能共享端点的边）在内部相交。

具体判断方法：

如果 $AB$ 与多边形的某条边（非相邻边）规范相交（交点不在端点），则 $AB$ 不在内部。

如果 $AB$ 的中点不在多边形内部，则 $AB$ 不在内部（但这里可能误判，所以用上一条更安全）。

更简单的方法： 对 $AB$ 与多边形每条边（除了与 $A,B$ 相邻的边）做线段相交检测，如果发现规范相交，则排除。

算法步骤

枚举所有顶点对 $(i,j)$。

检查线段 $P_i P_j$ 是否完全在多边形内部：

对 $k=0$ 到 $n-1$，检查边 $(P_k, P_{k+1})$ 与 $P_i P_j$ 是否规范相交（且 $k,k+1$ 不与 $i,j$ 相同或相邻）。

如果没有规范相交，并且 $P_i P_j$ 的中点通过射线法判断在多边形内部，则接受（或者更简单：因为无规范相交且端点在边界上，则整段在多边形内）。

记录最大长度。

特殊情况

如果多边形是凸的，那么任意两个顶点之间的线段都在多边形内部，直接求最远点对（旋转卡壳）即可 $O(n)$。

但题目没有保证凸性，所以必须检查每条线段。

时间复杂度

$O(n^3)$，$n \le 200$，可行。

示例代码（框架）

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

const double EPS = 1e-9;

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); } double operator*(const Point& p) const { return x * p.y - y * p.x; } // cross double len2() const { return xx + yy; } double len() const { return sqrt(len2()); } };

// 判断线段 (a,b) 与 (c,d) 是否规范相交 bool segmentIntersect(Point a, Point b, Point c, Point d) { double c1 = (b - a) * (c - a); double c2 = (b - a) * (d - a); double c3 = (d - c) * (a - c); double c4 = (d - c) * (b - c); if (c1 * c2 < -EPS && c3 * c4 < -EPS) return true; return false; }

// 判断点是否在线段上 bool onSegment(Point p, Point a, Point b) { return fabs((a - p) * (b - p)) < EPS && min(a.x, b.x) - EPS <= p.x && p.x <= max(a.x, b.x) + EPS && min(a.y, b.y) - EPS <= p.y && p.y <= max(a.y, b.y) + EPS; }

int n; vector poly;

// 检查线段 (poly[i], poly[j]) 是否完全在多边形内部 bool inside(int i, int j) { // 检查与多边形每条边是否规范相交 for (int k = 0; k < n; k++) { int nk = (k + 1) % n; if (k == i || k == j || nk == i || nk == j) continue; // 相邻边 if (segmentIntersect(poly[i], poly[j], poly[k], poly[nk])) return false; } // 取中点检查是否在多边形内部（射线法） Point mid((poly[i].x + poly[j].x) / 2, (poly[i].y + poly[j].y) / 2); int cnt = 0; for (int k = 0; k < n; k++) { Point a = poly[k], b = poly[(k + 1) % n]; if (onSegment(mid, a, b)) return true; // 中点在边上也算内部 if (a.y > b.y) swap(a, b); if (mid.y < a.y - EPS || mid.y > b.y - EPS) continue; double cross = (b - a) * (mid - a); if (cross > EPS) cnt++; } return cnt % 2 == 1; }

int main() { cin >> n; poly.resize(n); for (int i = 0; i < n; i++) { cin >> poly[i].x >> poly[i].y; } double ans = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (inside(i, j)) { ans = max(ans, (poly[i] - poly[j]).len()); } } } printf("%.9f\n", ans); return 0; }

总结

核心是枚举顶点对并检查线段是否完全在多边形内部。

检查方法：不与任何非相邻边规范相交，并且中点（或任意内点）在多边形内部。

$O(n^3)$ 在 $n \le 200$ 时可行。