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; }