欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HihoCoder - 1142 三分·三分求极值

程序员文章站 2022-07-13 13:52:50
...

#1142 : 三分·三分求极值

时间限制:10000ms  单点时限:1000ms  内存限制:256MB

题目描述

HihoCoder - 1142 三分·三分求极值

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

三分法:

从三分法的名字中可以猜到,三分法是对于需要逼近的区间做三等分:

HihoCoder - 1142 三分·三分求极值

发现lm这个点比rm要低,那么我们要找的最小点一定在[left,rm]之间。如果最低点在[rm,right]之间,就会出现在rm左右都有比他低的点,这显然是不可能的。 同理,当rm比lm低时,最低点一定在[lm,right]的区间内。
利用这个性质,我们就可以在缩小区间的同时向目标点逼近,从而得到极值。

题目上已经教我们怎么用三分法,接下来就写代码

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long  Lint;
const double esp = 1e-8;
double a,b,c,x,y;

double GetY(double x){
    return a*x*x+b*x+c;
}

double GetD(double x1,double y1,double x2,double y2){
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

void deal(){
    cin>>a>>b>>c>>x>>y;
    double l=-10000,r=10000,lm,rm;
    double dd;
    while(GetD(l,GetY(l),r,GetY(r))>esp){
        dd=(r-l)/3;
        lm=l+dd;
        rm=2*dd+l;
        double yy1=GetD(lm,GetY(lm),x,y);
        double yy2=GetD(rm,GetY(rm),x,y);
        if(yy1<yy2)
            r=rm;
        else
            l=lm;
    }
    printf("%.3f\n",GetD(l,GetY(l),x,y));
}

int main(){
    deal();
    return 0;
}