二分法作為分治中最常見的方法，適用于單調函數，逼近求解某點的值。但當函數是凸性函數時，二分法就無法適用，這時三分法就可以“大顯身手”～～
如圖，類似二分的定義Left和Right，mid = (Left + Right) / 2，midmid = (mid + Right) / 2; 如果mid靠近極值點，則Right = midmid；否則(即midmid靠近極值點)，則Left = mid;
程序模版如下：
double Calc(Type a)
{
/* 根據題目的意思計算 */
}
void Solve(void)
{
double Left, Right;
double mid, midmid;
double mid_value, midmid_value;
Left = MIN; Right = MAX;
while (Left + EPS < Right)
{
mid = (Left + Right) / 2;
midmid = (mid + Right) / 2;
mid_area = Calc(mid);
midmid_area = Calc(midmid);
// 假設求解最大極值.
if (mid_area >= midmid_area) Right = midmid;
else Left = mid;
}
}
現根據幾道的OJ題目來分析三分法的具體實現。
buaa 1033 Easy Problem
http://acm.buaa.edu.cn/oj/problem_show.php?c=0&p=1033
題意為在一條線段上找到一點，與給定的Ｐ點距離最小。很明顯的凸性函數，用三分法來解決。
Calc函數即為求某點到P點的距離。
ZOJ 3203 Light Bulb
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3203
如圖，人左右走動，求影子L的最長長度。
根據圖，很容易發現當燈，人的頭部和墻角成一條直線時(假設此時人站在A點)，此時的長度是影子全在地上的最長長度。當人再向右走時，影子開始投影到墻上，當人貼著墻，影子長度即為人的高度。所以當人從A點走到墻，函數是先遞增再遞減，為凸性函數，所以我們可以用三分法來求解。
下面只給出Calc函數，其他直接套模版即可。
double Calc(double x)
{
return (h * D - H * x) / (D - x) + x;
}
heru 5081 Turn the corner 08年哈爾濱regional網絡賽
http://acm.hrbeu.edu.cn/index.php?act=problem&id=1280
汽車拐彎問題，給定X, Y, l, d判斷是否能夠拐彎。首先當X或者Y小于d，那么一定不能。
其次我們發現隨著角度θ的增大，最大高度ｈ先增長后減小，即為凸性函數，可以用三分法來求解。
這里的Calc函數需要比較繁瑣的推倒公式：
s = l * cos(θ) + w * sin(θ) - x;
h = s * tan(θ) + w * cos(θ);
其中s為汽車最右邊的點離拐角的水平距離, h為里拐點最高的距離, θ范圍從0到90。
POJ 3301 Texas Trip
http://acm.pku.edu.cn/JudgeOnline/problem?id=3301
題意為給定n(n <= 30)個點，求出飽含這些點的面積最小的正方形。
有兩種解法，一種為逼近法，就是每次m分角度，求出最符合的角度，再繼續m分，如此進行times次，即可求出較為精確的解。(m 大概取10, times取30即可)
第二種解法即為三分法，首先旋轉的角度只要在0到180度即可，超過180度跟前面的相同的。坐標軸旋轉后，坐標變換為：
X’ = x * cosa - y * sina;
y’ = y * cosa + x * sina;
至于這題的函數是否是凸性的，為什么是凸性的，我也無法給出準確的證明，希望哪位路過的大牛指點一下～～
例題更新(2010.5.5)
hdu 3400 Line belt
http://acm.hdu.edu.cn/showproblem.php?pid=3400
典型的三分法，先三分第一條線段，找到一個點，然后根據這個點再三分第二條線段即可，想出三分的思路基本就可以過了。
對于求解一些實際問題，當公式難以推導出來時，二分、三分法可以較為精確地求解出一些臨界值，且效率也是令人滿意的。
/* czyuan原創，轉載請注明出處。*/
轉自：
http://hi.baidu.com/czyuan_acm/blog/item/8cc45b1f30cefefde1fe0b7e.html