壁毯照明——题解

问题理解

在多边形展厅中，我们需要确定是否存在一个放置灯的点，满足以下条件：

• 所有标记为 S 的墙面（墙）必须被完全照亮
• 所有标记为 C 的墙面必须完全不被照亮
• 灯不能放置在多边形的边界或顶点上

从几何角度看，"照亮"意味着灯与墙之间的连线完全在展厅内部，且灯位于该墙所在直线的特定一侧。

算法思路

核心思想：约束区域判定

解决此问题的关键是将照明约束转化为几何区域约束，通过判断这些约束区域的交集是否非空来确定解的存在性。

关键几何工具

1. 向量叉积运算

叉积是判断点与直线相对位置的核心工具：

ld operator^(const point &p1, const point &p2) {
    return p1.x * p2.y - p2.x * p1.y;
}

• 叉积结果为正：p2 在 p1 的左侧
• 叉积结果为负：p2 在 p1 的右侧
• 叉积结果为零：p1 与 p2 共线

2. 点的侧向判断

bool side_lt(point p1, point p2, point p3) {
    return ((p2 - p1) ^ (p3 - p2)) > 0;
}

该函数判断点 p3 位于线段 p1-p2 的哪一侧，这决定了点是否能"看到"该线段。

3. 线段相交检测

bool cross(point p1, point p2, point p3, point p4) {
    return (side_lt(p2, p1, p3)^side_lt(p2, p1, p4)) && 
           (side_lt(p4, p3, p1)^side_lt(p4, p3, p2));
}

使用跨立实验判断两条线段是否相交，用于检测视线是否被遮挡。

算法步骤

步骤1：数据预处理

• 读取多边形顶点坐标及各边类型（S 或 C）
• 复制顶点数组形成环形结构，便于处理多边形的循环特性

// 将多边形顶点和边信息复制一份，方便循环处理
for (int i = 1; i <= n; ++i)
    p[i + n] = p[i], val[i + n] = val[i];

步骤2：构建约束线段集

在 solve() 函数中，通过处理连续的非 S 边（C 边），构建连接两端 S 边的约束线段：

for (r = l, kt = l; l < n + kt; l = ++r) {
    if (!val[l]) {  // 当前边是 C 边
        while (!val[r]) ++r;  // 找到下一个 S 边
        // 检查几何约束并构建约束线段
        qj.push_back(line(p[l], p[r]));
    }
}

步骤3：验证约束可行性

check() 函数是核心验证模块，通过维护一个参数区间 [l, r] 来判断是否存在满足所有约束的点：

1. 对于 S 边：灯必须位于能照亮该边的一侧
2. 对于 C 边：灯必须位于无法照亮该边的一侧
3. 通过线段相交检测确保视线不被遮挡

bool check(point p1, point p2) {
    ld l = -INF, r = INF;  // 初始化可行区间
    bool fg = 0;
    
    // 处理所有约束线段
    for (auto i : qj) {
        // 计算交点参数并更新可行区间
        // ...
    }
    
    // 处理所有 S 边约束
    for (int i = 1; i <= n; ++i)
        if (val[i]) {
            // 检查 S 边约束并更新可行区间
            // ...
        }
    
    return l <= r;  // 区间非空则存在可行解
}

关键逻辑解析

1. 照明条件的几何转化：

   • 灯能照亮 S 边，等价于灯与该边的所有点连线不穿出多边形
   • 灯不能照亮 C 边，等价于灯位于该边的"阴影侧"

2. 参数化区间判断： query() 函数计算两直线交点的参数化表示，将几何约束转化为参数区间的交并运算，通过判断最终区间是否有效（l <= r）来确定解的存在性。

3. 特殊情况处理：

   • 所有边都是 S 时，直接检查是否存在能照亮所有边的点
   • 处理平行线段的特殊情况（叉积为零）
   • 确保灯的位置不在多边形边界上

复杂度分析

• 时间复杂度：$O(n^2)$，主要来自于对每条边的约束检查和线段相交判断
• 空间复杂度：$O(n)$，用于存储多边形顶点和约束线段集

学习要点

1. 几何问题的转化思维：将照明问题转化为几何约束区域的交运算
2. 叉积的灵活应用：掌握使用叉积判断点线位置关系的方法
3. 参数化方法：学习用参数区间表示可行解范围的技巧
4. 约束处理策略：如何将复杂问题分解为可验证的约束条件

通过这个问题，我们可以深入理解计算几何中"约束满足"类问题的求解思路，即将几何直观转化为可计算的代数条件，再通过系统的验证流程得到结果。