0395 勾股树
* * * *
拉格朗日计划
* * * *
勾股树

勾股树一种分形图形,可由如下步骤递归生成:

取一单位正方形开始,并以其中一条边为基底。

以基底所对的边作为斜边,给其粘上一个三边长之比为3-4-5的直角三角形。

给此直角三角形的两条直角边再分别粘上一个正方形,该直角边的长度即所粘连正方形的边长。

以正方形与之粘连的直角边作为基底,不断重复上述步骤。



以上过程中直角三角形较短的直角边应始终出现在基底的右侧。

勾股树是有界的,亦即存在一个四边都各自与初始正方形平行的长方形,使之能覆盖整棵勾股树。

求这样的长方形的最小面积,结果四舍五入到十位小数。

本题难度:



解答

此树的生成和绘制网络上能找到很多现成的资源和代码,具体形态取决于第一个直角三角形的三边之比,不过总体而言形如柳树,大致如下



要找到最小覆盖的矩形,主要是找出边界,此外,本题中的树在左下角处会低于基底,如下图



用$(s,x,y,t)$分别表示正方形的边长,左下角的坐标,与x轴的夹角(逆时针方向旋转轴,首次与一条边重合时转过的角度)作搜索,当变成小于预设的阈值时停止搜索。

阈值需要调试设置,最终结果是$28.2453753155$。

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

import math

epsilon=10**(-13)
a,b,c=4,3,5
xMin=yMin=0
xMax=yMax=1

r1,r2=a/c,b/c
dt1=math.acos(r1)
dt2=-math.acos(r2)

i=0
q=[(1,0,0,0)]
while i < len(q):
    s,x,y,t=q[i]
    xMin,xMax,yMin,yMax=min(xMin,x),max(xMax,x),min(yMin,y),max(yMax,y)
    dx,dy=s*math.cos(t),s*math.sin(t)
    x2,y2=x-dy,y+dx
    x3,y3=x2+((dx*r1)-(dy*r2))*r1,y2+((dx*r2)+(dy*r1))*r1
    da,db=s*a,s*b

    if s*r1>epsilon and (x2>xMax-da or x2 <  xMin+da or y2>yMax-da or y2 <  yMin+da):
        q.append((s*r1,x2,y2,t+dt1))
    if s*r2>epsilon and (x3>xMax-db or x3 < xMin+db or y3>yMax-db or y3 < yMin+db):
        q.append((s*r2,x3,y3,t+dt2))
    i+=1

print(f"{(xMax-xMin)*(yMax-yMin):.10f}")