💻 规矩出方圆
华为 · 计算几何 · 算法编程题
华为
计算几何
M ≤ 200
时限 1 秒 / 256 MB
题目描述
在边长为 1 的正方形画布上，圆心放在 (0.5, 0.5)，半径为 0.5 的圆恰好内切于画布。
我们要在水平方向与竖直方向各放置 M 条切割线（含边界 0 和 1，总共 M 条），把正方形分成 M×M 个小矩形。每个小矩形只要与圆的交集面积大于 1e-10，就视为“被染色”。当 M 为奇数时，期望通过巧妙地安排切割线的位置，使所有被染色的小矩形的总面积尽可能小，并输出这个最小面积，结果四舍五入到小数点后 4 位。 为简化问题，可以利用关于中心对称的性质：最优方案可以令横纵切割线共享同一组坐标。进一步地，若先确定所有横向坐标，那么每条横线与圆的两个交点会给出两条最合适的竖线位置，这样就能把优化变量收缩到一维（只需要优化横向坐标即可）。目标就是最小化由这些条带宽度与对应圆的水平截线宽度共同决定的“被染色面积”。
输入输出
输入描述
一行一个奇数 M，5 ≤ M ≤ 200。
输出描述
一行一个小数，为最小染色面积，保留 4 位小数（四舍五入）。
样例共 1 组
样例 1 · 当 M=9 时，采用中心对称、横纵同坐标的非等距切分，并将竖线对齐到每条横线与圆的交点附近，能把被染色矩形尽量“贴”着圆边，从而减少多余覆盖。使用数值优化求得的最小面积约为 0.8457，四舍五入后输出 0.8457。
输入
9
输出
0.8457
算法解析依据一般
考点：计算几何
数据规模 M ≤ 200 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出
题目画像
- 数据规模：M ≤ 200
- 复杂度门槛：允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
- 源站时限：1 秒（牛客口径，非本题专属门槛）
解题思路
参考方向：计算几何
把几何关系转成坐标运算，用整数运算避免浮点误差。
思路框架（计算几何 通法 · 非本题专属）
- 把点、向量、线段用坐标表示。
- 几何判定（平行、垂直、共线、相交）尽量用叉积/点积的整数形式：叉积为 0 即共线。
- 距离用平方比较，避免开方带来的浮点误差。
- 面积用叉积（鞋带公式）计算。
实现要点：叉积 cross = x1*y2 - x2*y1；用它判断顺时针/逆时针和共线。
复杂度：时间 O(n) ~ O(n²) ｜ 空间 O(n)
该范式的通法易错点
- 用浮点相等判断几何关系（应用整数叉积）。
- 没考虑三点共线、重合等退化情况。
对照本题
- 数据规模 M ≤ 200，允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
本题在源数据中没有官方考点标签，方向由题面特征推断，仅供参考。
样例解读
样例 1：输入 9 → 输出 0.8457
当 M=9 时，采用中心对称、横纵同坐标的非等距切分，并将竖线对齐到每条横线与圆的交点附近，能把被染色矩形尽量“贴”着圆边，从而减少多余覆盖。使用数值优化求得的最小面积约为 0.8457，四舍五入后输出 0.8457。
解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。
本题来源：2025年秋招-华为-11月05号AI岗。
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解