题目理解

我们有一个正方形牧场 $[-S,S] \times [-S,S]$，周围是无限大的土地。牧场内已有 $N$ 条栅栏，我们需要建造额外的栅栏将牧场完全围住，使得牛无法从牧场内走到外面的土地。目标是求建造栅栏的最小总长度。

问题分析

1. 问题本质

这是一个几何包围问题，需要在已有栅栏的基础上，用最短的额外栅栏将牧场完全隔离。

2. 关键观察

• 额外栅栏可以任意建造，可以与现有栅栏相交、重合
• 最终解决方案会形成一个闭合的包围圈
• 问题可以转化为在特定图上找最小环

算法思路

1. 图模型构建

将问题转化为图论问题：

• 节点：包括现有栅栏的端点（$2N$ 个）和牧场的四个角点（4个），共 $n = 2N+4$ 个节点
• 边：如果两个节点之间的线段不穿过牧场边界，则在这两个节点间建立边，权重为线段长度
• 边类型：用0/1标记边的"类型"，用于后续判断环的奇偶性

2. 核心数据结构

几何计算基础

struct Vector { db x, y; };  // 二维向量
struct Line { Vector a, b; }; // 线段

// 向量运算
Vector operator-(Vector a, Vector b);
db Cross(Vector a, Vector b);  // 叉积
db dis(Vector a, Vector b);    // 距离

// 点到线段的距离和垂足
pair<db, Vector> dis(Vector a, Line l);

图存储

db g[maxn][maxn][2];  // g[u][v][t] 表示从u到v类型为t的边的最短距离

3. 算法流程

步骤1：初始化图

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        g[i][j][0] = g[i][j][1] = inf;

步骤2：添加现有栅栏边

for (int i = 1; i <= N; i++) {
    add_edge(2*i-1, 2*i, a[i].a, a[i].b, 0);  // 现有栅栏本身
    add_edge(2*i, 2*i-1, a[i].b, a[i].a, 0);
}

步骤3：添加牧场边界边

for (int i = 0; i < 4; i++)
    for (int j = 0; j < 4; j++)
        if (i != j && valid(getp(i), getp(j)))
            add_edge(2*N+1+i, 2*N+1+j, getp(i), getp(j), 2*S);

步骤4：添加其他可行边

连接现有栅栏端点之间、栅栏端点与牧场角点之间的所有可行线段。

步骤5：Floyd求最小奇环

for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            for (int a = 0; a < 2; a++)
                for (int b = 0; b < 2; b++)
                    chkmin(g[i][j][a^b], g[i][k][a] + g[k][j][b]);

// 找最小奇环（类型为1的自环）
for (int i = 1; i <= n; i++)
    chkmin(ans, g[i][i][1]);

关键算法细节

1. 线段有效性检查

inline bool valid(Line l) {
    return !(seg_crossed(l, {getp(0), getp(1)}) ||  // 不穿过牧场边界
           seg_crossed(l, {getp(2), getp(3)}) ||
           seg_crossed(l, {getp(0), getp(3)}) ||
           seg_crossed(l, {Vector(0, -S), Vector(0, S)}));
}

2. 边类型标记

通过判断线段是否与某条测试射线相交来标记边的"类型"，用于后续判断环的奇偶性：

inline bool type(Line l) {
    return seg_crossed(l, {Vector(0, 0), Vector(0.114514, 1145.14)});
}

3. 点到线段的连接

对于每个点到每条线段，考虑三种连接方式：

• 连接到线段的垂足
• 连接到线段的起点
• 连接到线段的终点

复杂度分析

• 节点数: $O(N)$
• 边数: $O(N^2)$
• Floyd算法: $O(N^3)$
• 总复杂度: $O(N^3)$，对于 $N \leq 100$ 是可接受的

算法标签

• 计算几何: 向量运算、线段相交判断、点到线段距离
• 图论: 最短路径、最小环
• Floyd算法: 全源最短路径
• 几何建模: 将几何问题转化为图论问题

总结

这道题通过巧妙的几何到图论的转化，将复杂的栅栏包围问题转化为在特定图上寻找最小奇环的问题。算法的核心在于：

1. 几何基础: 准确的向量运算和相交判断
2. 图模型: 合理的节点和边设计
3. 奇环技巧: 通过边类型标记确保找到有效的包围圈
4. Floyd扩展: 在计算最短路径的同时跟踪路径类型

该解法充分利用了几何性质和图论算法的结合，是计算几何与图论交叉应用的典型范例。