此树的生成和绘制网络上能找到很多现成的资源和代码,具体形态取决于第一个直角三角形的三边之比,不过总体而言形如柳树,大致如下
要找到最小覆盖的矩形,主要是找出边界,此外,本题中的树在左下角处会低于基底,如下图
用$(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}")
|