圆周覆盖

令$R(a, b, c)$为三边长分别为a，b，c的三角形内部三个互不重叠的圆所能覆盖的最大面积。

对所有满足$1\le a\le b\le c < a+b\le n$的整数三元组$(a, b, c)$，记$S(n)$为所有$R(a, b, c)$的平均值。

可以验证$S(2)=R(1,1,1)\approx 0.31998, S(5)\approx1.25899$。

求$S(1803)$，结果保留小数点后5位。

本题难度:

解答

本题似乎直接贪心计算即可，能覆盖最大面积的三个圆可迭代生成，每次取当前各区域内接圆中的最大者即可。

亦即第一个圆是三角形的内接圆。在原三角形中去除内接圆，得相互分离的三部分，在每部分中分别取内接圆并选择其中最大的圆即为第二个圆，以此类推。

内接圆半径可由海伦公式计算。最终结果是$110242.87794$。

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

import math

n=1803

res=t=0
for a in range(1,n//2+1):
    for b in range(a,n-a+1):
        for c in range(b,a+b):
            s,sa,sb,sc=a+b+c,b+c-a,a+c-b,a+b-c
            d=sa*sb*sc/s
            r=0.5*math.sqrt(d)
            r2=0.25*d
            xa=math.sqrt(r2+0.25*sa*sa)
            ra=r*(xa-r)/(xa+r)
            xb=math.sqrt(r2+0.25*sb*sb)
            rb=r*(xb-r)/(xb+r)
            res+=(r2+ra*ra+max(ra*ra/r,rb)**2)*math.pi
            t+=1
    print(a,res,t)
print(f"{res/t:.5f}")