「BalticOI 2016 Day1」公园 题解

1. 题目解析

1.1 问题描述

有一个 $w \times h$ 的矩形公园，四个角落设有入口（编号 $1,2,3,4$）

公园内有 $n$ 棵圆形树（位置 $(x_i,y_i)$，半径 $r_i$）和 $m$ 个圆形游客（半径 $r$）

游客从指定入口进入，可以在公园内自由移动，但不能与任何树重叠

要求判断每个游客可以从哪些出口离开

1.2 关键约束

游客进出时必须与两条邻边相切

树与树之间不重叠

每个角落的 $2k \times 2k$ 区域没有树（$k$ 为最大游客半径）

重叠定义为有不止一个公共点

1.3 数据范围

$n \leq 2000$，$m \leq 10^5$

$4k \leq w,h \leq 10^9$

2. 算法思路

2.1 核心转化

几何问题 → 连通性问题：

将每棵树的半径扩大游客半径 $r$（Minkowski和）

游客缩小为点，问题转化为点能否在扩大后的障碍圆之间自由移动

四个入口作为图中的特殊节点

关键观察：

如果两棵树的扩大圆相交或相距很近，它们会阻挡游客通行

如果树与边界距离小于游客直径，会阻挡对应边界的通行

2.2 算法框架

并查集维护连通性：

将树和边界抽象为节点

用并查集维护它们之间的连通关系

当两棵树的距离小于游客直径时，合并它们所在的集合

当树与边界的距离小于游客直径时，标记该集合接触该边界

事件驱动处理：

预处理事件：

树-树之间的距离事件

树-四条边界之间的距离事件

按距离排序：

将所有事件按距离从小到大排序

将游客按半径从小到大排序

增量处理：

对于每个游客半径，处理所有距离小于 $2r$ 的事件

更新并查集和边界接触信息

2.3 边界连通性判断

边界编码：

左边界（$x=0$）：编码为 $1$

下边界（$y=0$）：编码为 $2$

右边界（$x=w$）：编码为 $4$

上边界（$y=h$）：编码为 $8$

关键规则：

如果一个连通分量同时接触左右边界（$1$ 和 $4$），则上下边界不连通

如果一个连通分量同时接触上下边界（$2$ 和 $8$），则左右边界不连通

相邻边界天然连通（如左下角连接边界 $1$ 和 $2$）

2.4 算法步骤

初始化：

为每棵树创建并查集节点

初始化所有边界对都是连通的

事件生成：

计算所有树对之间的距离

计算每棵树到四条边界的距离

处理查询：

按游客半径升序处理

增量合并距离小于 $2r$ 的树对

更新边界连通性

记录每个入口的可达出口

2.5 复杂度分析

时间复杂度：

事件数量：$O(n^2)$

排序：$O(n^2 \log n)$

并查集操作：$O(n^2 \alpha(n))$

查询处理：$O(m + n^2)$

空间复杂度：$O(n^2)$

3. 总结

本题展示了如何将复杂的几何运动问题转化为图论连通性问题：

核心技巧：

Minkowski和简化几何判断

事件驱动的增量处理

并查集维护动态连通性

边界条件的巧妙编码

算法优势：

避免了对每个查询的重复计算

利用排序和增量处理优化性能

适用于大规模查询场景

这种几何转化+并查集+事件驱动的解法在计算几何与图论结合的问题中具有广泛的适用性。