cor*_*ump 7 algorithm math geometry computational-geometry
我在准备比赛时遇到了以下有趣的问题.
你有一个三角形的长边a, b, c
和一根长绳L
.您需要找到具有最大表面积的绳索所包围的表面,并且必须完全位于三角形内.
所以,如果L = a + b + c
,那么它就是三角形的区域.
另外,我们知道圆周面的面积最大,所以如果L
小于或等于三角形内切圆的周长,那么该面积将是周长圆的面积L.
因此,剩下的情况是 alfa < L < a + b + c
,alfa
内切圆的周长在哪里.
任何想法都会很棒!
EDIT
:我想知道我是否应该专注于某种算法来解决这个问题,或者试图找出一个数学公式.比赛包含两者的组合.边长可以长达100,a,b,c,L
小数点后的精度为4位数.
..回答我自己的评论/问题,可以证明半径必须相等,
这是一个有用的公式:
灰色区域A为
A = r^2 ( alpha - Pi + 2/tan(alpha/2) ) /2
Run Code Online (Sandbox Code Playgroud)
但更有用......弧长很简单:
s = 2 ( b - A/r )
Run Code Online (Sandbox Code Playgroud)
从这里可以很容易地看出三个半径必须彼此相等:
写出绳子的长度和封闭面积:
ropelength = trianglelength - 2 Sum[r[i] a[i] ]
ropearea = trianglearea - Sum[r[i]^2 a[i] /2 ]
Run Code Online (Sandbox Code Playgroud)
在哪里
a[i]=( alpha[i] - Pi + 2/tan(alpha[i]/2) )
Run Code Online (Sandbox Code Playgroud)
经过一些操作后,最大化面积导致所有 r[i] 相等。请注意,三个 a[i]、ropelength、trainglearea、trianglelength 都是常数,不需要计算。迂腐地将 sub 求解r[l] = f( constants, r[2],r[3] )
到第二个表达式中,并求解
d ropearea /d r[2] = 0
和 ,d /d r[3] = 0
结果为:
r =(1/2) (triangle_length - rope_length) /(Sum(1/tan(alpha[i]/2)) - Pi)
Run Code Online (Sandbox Code Playgroud)
(a[i] 的混乱表达式仅在最后一步被替换)最后..
ropearea = trianglearea - (trianglelength-ropelength)^2/(8 Sum[a[i])
= trianglearea - (1/2)(trianglelength-ropelength) r
Run Code Online (Sandbox Code Playgroud)
编辑——一个有用的恒等式..a,b,c,边的长度。
Sum(1/tan(alpha[i]/2)) = Sqrt( S^3 / ((S-a)(S-b)(S-c)) )
S = 1/2 (a+b+c) ! S is semiperimeter not to be confused with arc length s
Run Code Online (Sandbox Code Playgroud)
上述表达式可用于重现内切圆的公式,
rinscribed = Sqrt( ((S-a)(S-b)(S-c)) / S )
Run Code Online (Sandbox Code Playgroud)