[BZOJ 1857] 传送带

Link:

BZOJ 1857 传送门

Solution:

首先中间的两个拐点$C,D$肯定都在传送带$A,B$上

接下来感性发现固定点A/C,另一个点C/D时间随位置的变化为单峰函数

这样就是三分套三分了

严谨的证明还不会啊……

目前好像只能推出仅有一个零点,不过不太会证单调性啊……

Code:

#include <bits/stdc++.h>

using namespace std;
#define X first
#define Y second
typedef long long ll;
typedef double db;
typedef pair<db,db> P;
const db eps=1e-;
P A,B,C,D,L,R;db p,q,r; void read(P &t){scanf("%lf%lf",&t.X,&t.Y);}
db dist(P a,P b){return sqrt((a.X-b.X)*(a.X-b.X)+(a.Y-b.Y)*(a.Y-b.Y));} db check(db rat)
{
R=P(C.X+(D.X-C.X)*rat,C.Y+(D.Y-C.Y)*rat);
return dist(R,D)/q+dist(L,R)/r;
}
db solve(db rat)
{
L=P(A.X+(B.X-A.X)*rat,A.Y+(B.Y-A.Y)*rat);
db l=,r=;
while(fabs(l-r)>eps)
{
db lm=l+(r-l)/3.0,rm=r-(r-l)/3.0;
if(check(lm)<check(rm)) r=rm; else l=lm;
}
return dist(A,L)/p+check((l+r)/2.0);
} int main()
{
read(A);read(B);read(C);read(D);
scanf("%lf%lf%lf",&p,&q,&r);
db l=,r=;
while(fabs(l-r)>eps)
{
db lm=l+(r-l)/3.0,rm=r-(r-l)/3.0;
if(solve(lm)<solve(rm)) r=rm; else l=lm;
}
printf("%.2lf",solve((l+r)/2.0));
return ;
}
上一篇:FileZilla server windows 2003系统下适用的版本


下一篇:Linux设备文件简介(转载)