点击打开链接
三分法介绍
在区间内用两个mid将区间分成三份，这样的查找算法称为三分查找,也就是三分法，三分法常用于求解单峰函数的最值。
二分法适用于单调函数，而单峰函数用二分明显不太好了，对于有些单峰函数，可以求导后转化为单调函数，从而使用二分，然而很多情况求导是很麻烦的，这时就需要用到三分了题意:给出抛物线y=ax^2+bx+c 和点(x,y) 求点到抛物线的最短距离d? 设(X,aX^2+bX+c)为抛物线上一点,则最短距离d=min(sqrt((x-X^2)+(y-aX^2+bX+c)^2)) d关于X变化而变化 若对d求导 求出极点p,后即可得到极值,但过程过于复杂 因为p为极点所以,[p,无穷大]递增,[无穷小,p]递减 d为单峰函数 用三分法逼近即可
#include <bits/stdc++.h> using namespace std; typedef long long ll; const double inf=1e5; const double eps=1e-4; double a,b,c,x,y; double cal(double X) { double dx=x-X; double dy=y-(a*X*X+b*X+c); return sqrt(dx*dx+dy*dy); } double Three_divide() { double l=-inf,r=inf; double m1,m2; while(l+eps<r) { m1=l+(r-l)/3; m2=r-(r-l)/3;//区间分成三份 double v1=cal(m1); double v2=cal(m2); if(v1<v2) r=m2; else l=m1; } return (m1+m2)/2; } int main() { while(cin>>a>>b>>c>>x>>y) { double ans=Three_divide(); ans=cal(ans); printf("%.3lf\n",ans); } return 0; }
