覆盖两块三角形作业面等价于覆盖它们的六个顶点。最小覆盖圆只取决于点集凸包,点数仅为 6,可暴力枚举候选圆:
在所有能覆盖的候选圆中取半径最小者。判断点是否在圆内时允许 10−9 量级误差。
施工现场有两块三角形作业面,需要用一顶圆形防尘罩把它们同时完全罩住。罩子可以放在平面上任意位置,半径可以任选,但必须覆盖两块三角形的全部区域。工地只关心半径越小越好,以便降低搭设成本。
保证每个三角形由三个不共线的顶点确定。答案为实数,设你的输出为 a、标准答案为 b,当且仅当 max(1,∣b∣)∣a−b∣≤0.000001 时视为正确。
约束:所有顶点坐标的绝对值不超过 102。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册