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

2019-11-14 10:01:42

字體：大中小

供稿：網(wǎng)友

1142 : 三分·三分求極值

時(shí)間限制:10000ms 單點(diǎn)時(shí)限:1000ms 內(nèi)存限制:256MB 描述這一次我們就簡(jiǎn)單一點(diǎn)了，題目在此：這里寫(xiě)圖片描述在直角坐標(biāo)系中有一條拋物線(xiàn)y=ax^2+bx+c和一個(gè)點(diǎn)P(x,y)，求點(diǎn)P到拋物線(xiàn)的最短距離d。提示：三分法輸入第1行：5個(gè)整數(shù)a,b,c,x,y。前三個(gè)數(shù)構(gòu)成拋物線(xiàn)的參數(shù)，后兩個(gè)數(shù)x,y表示P點(diǎn)坐標(biāo)。-200≤a,b,c,x,y≤200 輸出第1行：1個(gè)實(shí)數(shù)d，保留3位小數(shù)(四舍五入) 樣例輸入 2 8 2 -2 6 樣例輸出 2.437

/*三分答案.今天晚上感性的認(rèn)識(shí)了三分答案求法.然后接觸了對(duì)函數(shù)求導(dǎo)轉(zhuǎn)二分的思想.這題是用三分做的.由點(diǎn)到直線(xiàn)的距離公式得f(x)=sqrt((x-qx)*(x-qx)+(a*x*x+b*x+c-qy)*(a*x*x+b*x+c-qy)).展開(kāi)后對(duì)f(x)進(jìn)行二階求導(dǎo)可以知道它是一個(gè)凸形函數(shù)(我并沒(méi)有求orz)然后三分就可以了.搞個(gè)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.完全是為了練英語(yǔ)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; }