hicoder1142 三分求极值

在直角坐标系中有一条抛物线y=ax^2+bx+c和一个点P(x,y)，求点P到抛物线的最短距离d。

我们代入公式，有：

$d = min(\sqrt{(X - x)^2+(aX^2+bX+c-y)^2})$

由题面不难发现它是个下凸函数，于是就可以跑三分了

#include<bits/stdc++.h>

using namespace std;

const double esp=1e-;

double a,b,c,x,y;

double dis(double px){

    double py=a*px*px+b*px+c;

    return sqrt((x-px)*(x-px)+(y-py)*(y-py));

}

int main(){

    scanf("%lf%lf%lf%lf%lf",&a,&b,&c,&x,&y);

    double l=-200.0,r=200.0;

    while(l+esp<r){

        double lmid=l+(r-l)/,rmid=r-(r-l)/;

        if(dis(lmid)<dis(rmid))r=rmid;

        else l=lmid;

    }

    printf("%.3lf",dis(l));

    return ;

}

巴特西

hicoder1142 三分求极值

最新文章

热门文章