三分法求点到抛物线的最短距离
首先三分法简单说就是判断序列的最大最小值,该序列为一个凸性函数。通俗来讲,就是该序列必须有一个最大值(或最小值),在最大值(最小值)的左侧序列,必须满足不严格单调递增(递减),右侧序列必须满足不严格单调递减(递增)。
图片来源:https://blog.csdn.net/beiyouyu/article/details/7875480
然后再对二分进行二分,
我们mid比midmid更靠近最值,我们就舍弃右区间,否则我们舍弃左区间。
比较mid与midmid谁最靠近最值,只需要确定mid所在的函数值与midmid所在的函数值的大小。当最值为最大值时,mid与midmid中较大的那个自然更为靠近最值。最值为最小值时同理。
题目:已知点p(x,y),求点p到y=ax^2+bx+c的最短距离。
输入:a,b,c,x,y.(高精度)。
输入:最短距离(保留3位小数)
样例输入:16 107 8 75 173
输出:73.706
其实这题还蛮有坑点的,
首先要明白距离d的公式:即 d = min{ sqrt( (X − x)^2 + (aX^2 + bX + c − y)^2) },化简后也对于d的公式也满足凸性函数。
其实在高精度比较时,不能用<,>,==直接比较
#include<bits/stdc++.h>
using namespace std;
double a, b, c, x, y;
double judge(double xx){
return sqrt((xx-x)*(xx-x)+(a*xx*xx+b*xx+c-y)*(a*xx*xx+b*xx+c-y));
}
int main(){
while (~scanf("%lf%lf%lf%lf%lf", &a, &b, &c, &x, &y)){
double l=-1000,r=1000;
while(r-l>=0.00001){//double型比较
double mid = (l+r)/2;
double midd = (mid+r)/2;
if(judge(mid)<=judge(midd)) //判断在左区间还是右区间
r=midd; //最小值在左边我们就舍弃右区间
else
l=mid;//反之
}
printf("%.5f\n",judge(l));
}
return 0;
}