无解题田野的思路（代码仅供思考，不正确）
2026-04-15 19:54:27
发布于：浙江
该问题本质上是求解一组线段的最小周长包围轮廓，即计算这些线段的凸包周长。由于题目要求的是“infimum of fence total length”，也就是最小可能的围栏长度，因此我们只需计算所有线段所构成的凸包的周长即可。
使用凸包算法计算所有线段端点构成的最小包围轮廓。
通过计算凸包顶点之间的距离之和，得到最小周长。
精度控制在1e-6以内，满足题目要求。
1.输入处理：
读取峡谷（线段）的数量 n
对于每条线段，读取其两个端点坐标 (a_i, b_i) 和 (c_i, d_i)
将所有线段的端点存储在点集合中
凸包算法实现：
首先对所有点按照 x 坐标升序排序，若 x 相同则按 y 坐标升序排序
使用 Graham 扫描算法构建凸包：
从最左边的点开始，按逆时针方向扫描
对于每个新点，判断其是否在当前凸包的“左侧”（通过叉积判断）
如果在右侧，则移除最近加入的点，直到满足凸包性质
重复此过程直到所有点都被处理
再从右向左扫描，处理上凸包部分
2.周长计算：
凸包构建完成后，计算相邻顶点之间的欧几里得距离
将所有边长累加得到凸包周长
输出结果：
输出计算得到的凸包周长，保留适当精度
该算法的核心思想是利用凸包的性质：对于任意一组点，其凸包是包含所有点的最小凸多边形，因此凸包的周长就是所需围栏的最小长度。
通过凸包算法，我们能够准确找到包含所有线段的最小边界轮廓，从而得到围栏总长度的下确界。这种实现方式确保了结果的精确性和效率，满足题目对精度的要求。
凸包算法的详细步骤：
#include <bits/stdc++.h>
using namespace std;
// 定义点结构
struct Point {
double x, y;
Point() {}
Point(double x, double y) : x(x), y(y) {}
};
// 计算向量叉积
double cross(const Point &a, const Point &b, const Point &c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
// 计算两点间距离
double distance(const Point &a, const Point &b) {
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
// 比较函数：按x坐标升序，x相同时按y坐标升序
bool compare(const Point &a, const Point &b) {
if (a.x != b.x) return a.x < b.x;
return a.y < b.y;
}
// Andrew算法计算凸包
vector<Point> convex_hull(vector<Point> points) {
// 预处理：排序
sort(points.begin(), points.end(), compare);
// 去除重复点
points.erase(unique(points.begin(), points.end()), points.end());
int n = points.size();
if (n <= 1) return points;
vector<Point> hull;
// 构建下凸包
for (int i = 0; i < n; i++) {
// 当新点与已构建凸包的最后两个点构成的向量为顺时针时，删除最后一个点
while (hull.size() >= 2 && cross(hull[hull.size()-2], hull[hull.size()-1], points[i]) <= 0) {
hull.pop_back();
}
hull.push_back(points[i]);
}
// 记录下凸包的大小
int lower_size = hull.size();
// 构建上凸包
for (int i = n - 2; i >= 0; i--) {
// 当新点与已构建凸包的最后两个点构成的向量为顺时针时，删除最后一个点
while (hull.size() > lower_size && cross(hull[hull.size()-2], hull[hull.size()-1], points[i]) <= 0) {
hull.pop_back();
}
hull.push_back(points[i]);
}
// 移除重复的起点
if (hull.size() > 1) hull.pop_back();
return hull;
}
int main() {
int n;
cin >> n;
vector<Point> points(n);
for (int i = 0; i < n; i++) {
cin >> points[i].x >> points[i].y;
}
// 计算凸包
vector<Point> hull = convex_hull(points);
// 计算周长
double perimeter = 0;
for (int i = 0; i < hull.size(); i++) {
perimeter += distance(hull[i], hull[(i + 1) % hull.size()]);
}
// 输出结果
cout << fixed << setprecision(10) << perimeter << endl;
return 0;
}
自己解希望有一天通过率不是0.00%
有帮助，赞一个