HihoCoder - 1142 三分·三分求极值
程序员文章站
2022-07-13 13:52:50
...
#1142 : 三分·三分求极值
时间限制:10000ms 单点时限:1000ms 内存限制:256MB
题目描述
在直角坐标系中有一条抛物线y=ax^2+bx+c和一个点P(x,y),求点P到抛物线的最短距离d。
三分法:
从三分法的名字中可以猜到,三分法是对于需要逼近的区间做三等分:
发现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;
}
上一篇: P3382 【模板】三分法,难度⭐⭐⭐