首页 > 试题广场 >

规矩出方圆

[编程题]规矩出方圆
  • 热度指数:99 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
在边长为 1 的正方形画布上,圆心放在 (0.5, 0.5),半径为 0.5 的圆恰好内切于画布。

我们要在水平方向与竖直方向各放置 M 条切割线(含边界 0 和 1,总共 M 条),把正方形分成 M×M 个小矩形。每个小矩形只要与圆的交集面积大于 1e-10,就视为“被染色”。当 M 为奇数时,期望通过巧妙地安排切割线的位置,使所有被染色的小矩形的总面积尽可能小,并输出这个最小面积,结果四舍五入到小数点后 4 位。

为简化问题,可以利用关于中心对称的性质:最优方案可以令横纵切割线共享同一组坐标。进一步地,若先确定所有横向坐标,那么每条横线与圆的两个交点会给出两条最合适的竖线位置,这样就能把优化变量收缩到一维(只需要优化横向坐标即可)。目标就是最小化由这些条带宽度与对应圆的水平截线宽度共同决定的“被染色面积”。


输入描述:
一行一个奇数 M,5 ≤ M ≤ 200。


输出描述:
一行一个小数,为最小染色面积,保留 4 位小数(四舍五入)。

示例1

输入

9

输出

0.8457

说明

当 M=9 时,采用中心对称、横纵同坐标的非等距切分,并将竖线对齐到每条横线与圆的交点附近,能把被染色矩形尽量“贴”着圆边,从而减少多余覆盖。使用数值优化求得的最小面积约为 0.8457,四舍五入后输出 0.8457。

备注:
本题由牛友@Charles 整理上传

这道题你会答吗?花几分钟告诉大家答案吧!