三分求单峰/单谷函数极值

单峰函数：拥有唯一的极大值点，在极大值点左侧严格单增，右侧严格单减。函数值先增大后减小。

单谷函数：拥有唯一的极小值点，在极小值点左侧严格单减，右侧严格单增。函数值先减小后增大。

1.求单峰函数的极大值点：

在函数定义域[left,right]上取两个点lmid和rmid将函数分为三段。

（1）若f(lmid)

（2）同理，若f(lmid)>f(rmid)，则极大值点一定在rmid左侧，因此可令right=rmid。

lmid=left+(right-left)/3=(2*left+right)/3;

rmid=right-(right-left)/3=(left+2*right)/3;

//求解极大值点
double th_division(double left,double right,double eps){
	double lmid,rmid;
	while(left+eps<right){
	    lmid=(2*left+right)/3;
	    rmid=(left+2*right)/3;
	    if(f(lmid)<f(rmid)){
	    	//表明lmid和rmid要么在同侧且上升，那么lmid肯定在波谷的左边
			//所以令left=lmid; 
	    	left=lmid;
		}
		//否则令right=rmid; 
		else right=rmid;
	}
	return lmid;
} 

2.求单谷函数的极小值点

原理同上

//求解极小值点
double th_division(double left,double right,double eps){
	double lmid,rmid;
	while(left+eps<right){
	    lmid=(2*left+right)/3;
	    rmid=(left+2*right)/3;
	    if(f(lmid)>f(rmid)){
	    	//表明lmid和rmid要么在同侧且下降，那么lmid肯定在波谷的左边
			//所以令left=lmid; 
	    	left=lmid;
		}
		//否则令right=rmid; 
		else right=rmid;
	}
	return lmid;
} 

例题：

HDOJ2438 Turn the corner

题意：

给出转角的两个宽度x,y和车的长度和宽度l和d，问车能否成功通过转角。

思路：

如图：

转弯时，假设汽车的一边紧贴转角，

则要想通过转角，则需

 

因为

又因为  

所以

我们发现随着从0°增长到90°，h先增大后减小，是凸性函数。因此用三分求出极大值点，如果最大值<=y，表明可以通过转角，否则不能通过。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double pi=acos(-1.0),eps=1e-10;
double x,y,l,d;
double f(double seta){//seta即为图中的角 
	double p=(x-d/cos(seta))/sin(seta);
	double h=l*cos(seta)-p*cos(seta);
	//seta角从0°增长到90°，h先增大后减小，为凸性函数，因此利用三分求极大值点 
	return h;
} 
 
int main(){
	while(scanf("%lf%lf%lf%lf",&x,&y,&l,&d)!=EOF){
		double left=0.0,right=pi/2;
		double lmid,rmid;
		while(left+eps<right){//三分 
			lmid=(2*left+right)/3;
			rmid=(left+2*right)/3;
			if(f(lmid)<f(rmid)){
				left=lmid;
			}
			else right=rmid;
		}
		//如果最大值f(left)<=y，表示可以通过 
		if(f(left)<=y) puts("yes");
		else puts("no");
	}
	return 0;
}

ZOJ 3203 Light Bulb

题意：

给出H,h,D,求影子的长度。

思路：

影子的长度为地上的和墙上的影子长度之和。

利用角度和相似三角形可以求出len的表达式，发现随着x从小到大，len先增大后减小，因此为凸性函数，利用三分求解。

 

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double pi=acos(-1.0),eps=1e-10;
double H,h,D;
double f(double x){ 
	return D-x+h-(D-x)*(H-h)/x;
} 
 
int main(){
	int t;
	scanf("%d",&t);
    while(t--){
    	scanf("%lf%lf%lf",&H,&h,&D);
		double left=0.0,right=D;
		double lmid,rmid;
		while(left+eps<right){//三分 
			lmid=(2*left+right)/3;
			rmid=(left+2*right)/3;
			if(f(lmid)<f(rmid)){
				left=lmid;
			}
			else right=rmid;
		}
		 
		printf("%.3lf\n",f(left));
	}
	return 0;
}