Hihocoder #1142 : 三分·三分求极值

2019-11-14 09:28:17

字体：大中小

来源：转载

供稿：网友

1142 : 三分·三分求极值

时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述这一次我们就简单一点了，题目在此：这里写图片描述在直角坐标系中有一条抛物线y=ax^2+bx+c和一个点P(x,y)，求点P到抛物线的最短距离d。提示：三分法输入第1行：5个整数a,b,c,x,y。前三个数构成抛物线的参数，后两个数x,y表示P点坐标。-200≤a,b,c,x,y≤200 输出第1行：1个实数d，保留3位小数(四舍五入) 样例输入 2 8 2 -2 6 样例输出 2.437

/*三分答案.今天晚上感性的认识了三分答案求法.然后接触了对函数求导转二分的思想.这题是用三分做的.由点到直线的距离公式得f(x)=sqrt((x-qx)*(x-qx)+(a*x*x+b*x+c-qy)*(a*x*x+b*x+c-qy)).展开后对f(x)进行二阶求导可以知道它是一个凸形函数(我并没有求orz)然后三分就可以了.搞个mid,midmid.case 1:area(mid)>=area(midmid) so the mid is nearer than midmid(or same) then change r to midmid.case 2:area(mid)<area(midmid) so the midmid is nearer than mid then change l to mid.完全是为了练英语hhh. */#include<cstdio>#include<cmath>#define MAXN 101#define eps 1e-7using namespace std;double l=-1e3,r=1e3,ans,a,b,c,qx,qy;double check(double x){ return sqrt((x-qx)*(x-qx)+(a*x*x+b*x+c-qy)*(a*x*x+b*x+c-qy));}void sanfen(){ double mid,midmid; while(l+eps<r) { mid=(l+r)/2;midmid=(mid+r)/2; if(check(mid)>=check(midmid)) l=mid,ans=mid; else r=midmid; } PRintf("%.3f",check(ans)); return ; return ;}int main(){ scanf("%lf%lf%lf",&a,&b,&c); scanf("%lf%lf",&qx,&qy); sanfen(); return 0;}

上一篇：1036. Boys vs Girls (25)

下一篇：当GridView数据为空时，解决表格不显示的问题