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}\),显然有:

$$ sin(\angle{GAH})=\frac{GI}{GA}=1-t \Rightarrow \angle{GAH}= asin(1-t) $$

则扇形\(\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}\)的面积为:

$$ S_{\widehat{GJH}}=\frac{1}{2}asin(1-t)-\frac{1}{2}(1-t)(1-\frac{1}{n}) $$

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

$$ S_{\widehat{FGH}}=S_{\triangle{FJH}}-S_{\widehat{GJH}}=\frac{1}{2n}-\frac{1}{2}asin(1-t)+\frac{1}{2}(1-t)(1-\frac{1}{n}) $$

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

$$ t=\displaystyle \frac{n^{2} + n - \sqrt{2} n^{1.5}}{n^{2} + 1} $$

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

$$ r(n)=\displaystyle \frac{\frac{\left(1 - \frac{1}{n}\right) \left(1 - \frac{n^{2} + n - \sqrt{2} n^{1.5}}{n^{2} + 1}\right)}{2} - \frac{\operatorname{asin}{\left(1 - \frac{n^{2} + n - \sqrt{2} n^{1.5}}{n^{2} + 1} \right)}}{2} + \frac{1}{2 n}}{1 - \frac{\pi}{4}} $$

当我们代入\(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