← 题库COVERING PROBLEMS

覆盖问题

用若干全等图形完整覆盖目标容器，不留任何未被遮盖的空隙，并使图形的共同尺寸尽可能小。本页汇集站内全部连续覆盖题族，包含等圆覆盖与正多边形覆盖。

题族6

子题127

仍然开放122

有外部构型92

覆盖与装箱正好相反

装箱问题禁止图形重叠、要求留在容器内部，并最大化图形尺寸；覆盖问题则允许图形相互重叠或伸出容器边界，但要求容器内的每一点都至少被一块图形覆盖，并最小化共同尺寸。边界、角点以及图形交界处的微小缝隙往往直接决定最终得分。

站内验证器不采用像素网格采样。对于等圆覆盖，验证器精确枚举 Voronoi 顶点及容器边界交点等有限候选最远点；对于多边形覆盖，验证器构造边与交点的平面排列并执行精确扫描。因此，有限小数坐标能够严格证明整个连续区域已被完全覆盖。

在单位正方形内放置 n 个圆心，使覆盖整个正方形所需的等圆共同半径最小。

在单位正三角形中放 n 个圆心，让覆盖整个三角形所需的共同半径尽可能小。

在正五边形内布置 n 个圆心，使覆盖整个容器所需的共同半径尽可能小。

用 n 个全等正三角形覆盖单位正方形。每块可自由平移、旋转和翻转，允许重叠与伸出容器，使共同边长尽可能小。

用 n 个全等正三角形覆盖单位正三角形；每块可独立平移、旋转和翻转，使共同边长尽可能小。

用 n 个全等正三角形覆盖单位圆盘；每块可独立平移、旋转和翻转，使共同边长尽可能小。