587. 凹三角形(Concave triangle)

如下图左所示，在一个圆外作外接正方形，我们称蓝色阴影区域为L型块。如下图右所示，从正方形的左下角向右上角画一条直线，我们称橙色阴影区域为凹三角形，显然此时凹三角形的面积是L型块的一半。：

如下图所示，将两个圆水平并排摆放，并作一个外接长方形，并从左下角向右上角画一条直线，此时凹三角形的面积是L型块的约36.46%：

将\(n\)个圆水平并排摆放，并作一个外接长方形，并从左下角向右上角画一条直线，可以计算得出，使得此时凹三角形面积少于L型块的10%的最小的\(n=15\)。求使得凹三角形面积少于L型块的0.1%的最小的\(n\)值是多少？

分析：这道题的基本思路并不困难，我们很容易知道\(L\)型块的面积应该是正方形的面积减去内接员的面积再除以四，因为题目只关心比例，为简化起见，不妨设内接圆的半径为\(1\)，则正方形的边长为\(2\)，则\(S_{L}=\frac{4-\pi}{4}=1-\frac{\pi}{4}\)。现在只需要知道求黄色阴影部分的面积再计算比值即可。为了方便后面的求解和描述，我们首先来建立一个坐标系，以外接矩形左下角顶点为原点，同时为了图示方便，坐标系中我们只画了两个内接圆，但是求解的原理也可以适用于\(n\)个圆的情况，图示如下：

上图中，直线\(FD\)与第一个圆相交于\(G\)点，对应\(G\)点的横坐标设为\(t\)，则因为直线\(FD\)的斜率为\(1/n\)，则\(G\)点的纵坐标为\(t/n\)。我们要求的是\(\widehat{FGH}\)的面积，它显然等于三角形\(\triangle{FJH}\)的面积减去弓形\(\widehat{GJH}\)的面积，而弓形\(\widehat{GJH}\)的面积又等于扇形\(\widehat{AGH}\)的面积减去三角形\(\triangle{AGJ}\)的面积。首先来看扇形\(\widehat{AGH}\)的面积，使用弧度面积公式，扇形的面积为\(\frac{1}{2}\alpha r^2\)，其中\(\alpha\)为扇形对应的弧度，在这里就是\(\angle{GAH}\)，显然有：

则扇形\(\widehat{AGH}\)的面积为\(\frac{1}{2}asin(1-t)\)。同时因为\(HJ=1/n\)，则\(AJ=1-1/n\)，则三角形\(\triangle{AGJ}\)的面积为\(\frac{1}{2}(1-t)(1-\frac{1}{n})\)，因此求得弓形\(\widehat{GJH}\)的面积为：

而三角形\(\triangle{FJH}\)的面积显然为\(1/2n\)，则弓形\(\widehat{FGH}\)的面积为：

在求解出以上面积后，我们只需要求解出\(G\)点对应的横坐标也就是\(t\)即可，因直线\(FD\)的表述式为\(y=x/n\)，则圆\(A\)的方程为\((x-1)^2+(y-1)^2=1\)，则联立两个方程并取其中较小的解，则有：

我们将以上表达式代入弓形\(\widehat{FGH}\)的面积的公式并除以\(S_{L}=1-\frac{\pi}{4}\)，则比值应为\(n\)的函数，即：

当我们代入\(n=1\)时有\(r(1)=0.5\)；代入\(n=2\)时有\(r(2)\approx0.3646\)，与题目中给出的条件相符。我们现在只需要对以上表达式迭代求解，找到第一个比例小于0.1%的\(n\)值即可。代码如下：

# time cost = 2.92 ms ± 98.5 µs

from math import sqrt,asin,pi    

def t(n):
    res = (n**2+n-sqrt(2)*n**1.5)/(n**2+1)
    return res

def area(t,n):
    res = 1/(2*n) - asin(1-t)/2 + (1-t)*(1-1/n)/2
    return res

def main(N=0.001):
    i = 100
    while True:
        if area(t(i),i)/(1-pi/4) < N:
            return i
        else:
            i = i + 1