0
0
0
1. 云栖社区>
2. 博客>
3. 正文

## 三分搜索法

如图，类似二分的定义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;
}
}

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

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

s = l * cos(θ) + w * sin(θ) - x;
h = s * tan(θ) + w * cos(θ);

POJ 3301 Texas Trip
http://acm.pku.edu.cn/JudgeOnline/problem?id=3301

X’ = x * cosa - y * sina;
y’ = y * cosa + x * sina;

hdu 3400 Line belt

http://acm.hdu.edu.cn/showproblem.php?pid=3400

（转自http://hi.baidu.com/czyuan_acm/blog/item/8cc45b1f30cefefde1fe0b7e.html

+ 关注

corcosa 13680人浏览