UVa 11281 -- TRIANGULAR PEGS IN ROUND HOLES

簡單題。

http://uva.onlinejudge.org/external/112/11281.html

給定三角形，求最小半徑的圓洞 x，讓三角形 PEGS 剛好通過圓洞。

第一個想法是求三角形外接圓半徑。

T = sqrt[p(p-a)(p-b)(p-c)] = abc/(4R)，其中 p = (a+b+c)/2 三角形半周長，

這樣可以得出 R。

x = R，是嗎？



但如果是鈍角三角形，這樣的 R 似乎又太大了，

考慮退化三角形，線段 ((此時 R 為無窮大))，只要線段通過圓洞就可以了。

x = max(a/2, b/2, c/2)

鈍角三角形判斷可以利用餘弦定理，

a^2 = b^2 + c^2 - 2bc cos(A)，當 A > 90度，cos(A) < 0，

此時 a^2 > b^2 + c^2，a 為最長邊，x = a/2。

((大角對大邊，不會有第二個角 > 90 度，因為三角形內角和 180 度))

https://github.com/Meng-Gen/UVa/blob/master/UVa/acm_11281.cc



加強版類似題，TopCoder TVTower (SRM 183 Division I Level 2)

http://community.topcoder.com/stat?c=problem_statement&pm=2260&rd=4735

Divide and conquer