设计方案ppt模板,windows优化大师卸载,番禺区画册设计公司,做网站有回扣拿吗http://www.lydsy.com/JudgeOnline/problem.php?id1857 Description 在一个2维平面上有两条传送带#xff0c;每一条传送带可以看成是一条线段。两条传送带分别为线段AB和线段CD。lxhgww在AB上的移动速度为P#xff0c;在CD上的移动速度为Q#xff0c;在平面上的移动速度R。…http://www.lydsy.com/JudgeOnline/problem.php?id1857 Description 在一个2维平面上有两条传送带每一条传送带可以看成是一条线段。两条传送带分别为线段AB和线段CD。lxhgww在AB上的移动速度为P在CD上的移动速度为Q在平面上的移动速度R。现在lxhgww想从A点走到D点他想知道最少需要走多长时间 Input 输入数据第一行是4个整数表示A和B的坐标分别为AxAyBxBy 第二行是4个整数表示C和D的坐标分别为CxCyDxDy 第三行是3个整数分别是PQR Output 输出数据为一行表示lxhgww从A点走到D点的最短时间保留到小数点后2位 Sample Input 0 0 0 100 100 0 100 100 2 2 1 Sample Output 136.60 HINT 对于100%的数据1 AxAyBxByCxCyDxDy1000 1PQR10 —————————————————————————————— 首先我们取AB一点ECD一点F则我们跑了AEEFFD。 考虑将其中一个点固定住那么显然对于另一个点我们三分即可求出这个店的位置显然该点有最小值他的左右两点都比他大所以为单峰函数。 那么对于最开始的点我们同样也是单峰函数也可以三分通过神奇的代数几何可以证明 所以这题就是三分套三分。 PS因为这题x1与x2可能相同所以不能单独三分x或y必须同时三分不然代码量太大了 #includecstdio
#includecmath
#includealgorithm
#includecstring
#includeiostream
using namespace std;
typedef double dl;
const int N100;
dl ax,ay,bx,by,cx,cy,dx,dy,P,Q,R;
inline dl dis(dl x,dl y,dl xx,dl yy){return sqrt((x-xx)*(x-xx)(y-yy)*(y-yy));
}
dl sff(dl x,dl y){dl lxcx,rxdx,lycy,rydy;dl lfx,lfy,rfx,rfy;for(int i1;iN;i){lfx(lx*2rx)/3;lfy(ly*2ry)/3;rfx(lfxrx)/2;rfy(lfyry)/2;dl t1dis(lfx,lfy,dx,dy)/Qdis(lfx,lfy,x,y)/R;dl t2dis(rfx,rfy,dx,dy)/Qdis(rfx,rfy,x,y)/R;if(t1t2){rxrfx;ryrfy;}else{lxlfx;lylfy;}}return dis(lx,ly,dx,dy)/Qdis(lx,ly,x,y)/Rdis(x,y,ax,ay)/P;
}
dl sfe(dl lx,dl rx,dl ly,dl ry){dl lex,ley,rex,rey;for(int i1;iN;i){lex(lx*2rx)/3;ley(ly*2ry)/3;rex(lexrx)/2;rey(leyry)/2;if(sff(lex,ley)sff(rex,rey)){rxrex;ryrey;}else{lxlex;lyley;}}return sff(lx,ly);
}
int main(){cinaxaybxbycxcydxdyPQR;printf(%.2lf\n,sfe(ax,bx,ay,by));return 0;
} 转载于:https://www.cnblogs.com/luyouqi233/p/8007039.html
