0392 单位圆陷阱
* * * *
拉格朗日计划
* * * *
跳跃游戏

非等距网格是指网格线间距不一定相等的网格,例如对数坐标就是一种非等距网格。

考虑直角坐标系下以$x=\pm 1$ 和 $y=\pm1$为边界、且所有网格线均平行于坐标轴的$(n+1)\times(n+1)$的非等距网格。

与单位圆相交的单元格染红色,不相交的染黑色。

给定n,找出能使红色单元格占据的总面积最小的划分方法。例如下图是$n=10$时的最优解,此时红色单元格的总面积四舍五入到小数点后10位为3.3469640797。



求$n=400$时红色单元格占据的最小总面积,四舍五入到小数点后10位。

本题难度:



解答

不难看出最优解一定是关于坐标轴对称的,因此可以只考虑第一象限的分割情况。

令$m=n/2$,并设垂直分割线的横坐标从小到大依次是 $$x_0=0 < x_1 < x_2 < \ldots < x_m < 1=x_{m+1},$$ 水平分割线的纵坐标从小到大依次是 $$y_0=0 < y_1 < y_2 < \ldots < y_m < 1=y_{m+1},$$ 那么本题就是要令 $$\sum_{i=1}^m\sum(x_{i+1}-x_i)(y_{m+1}-y_{m+1-i}),$$ 最小。这是一个多元优化问题,可以任选一组初值(比如等距分割)计算梯度迭代求解。不过对于本问题而言有这样一个观察:

最优分割中与红色区域相邻的黑色区域(只考虑第一象限),其左下角与圆周相交,且左上到右下的对角线平行于此交点处圆的切线。

满足上述性质的分割可由一条分割线唯一确定,因此利用二分搜索确定起点$x_1$的坐标即可得结果$3.1486734435$。

注:为便于作除法和格式化输出,以下代码为Python 3。

import math

bound=200
epsilon=10**(-11)
a,b,x1=0.0,1.0,0.0
while abs(x1-1)>=epsilon:
    area=x1=c=0.5*(a+b)
    i,y0=0,1
    while x1 <= 1 and i < bound:
        y1=math.sqrt(1-x1*x1)
        dx=(y0-y1)*y1/x1
        area+=dx*y1
        x1+=dx
        y0=y1
        i+=1
    if x1>1:
        b=c
    else:
        a=c

print(f"{4*area:.10f}")