hdu 3400 Line belt 三分法

时间:2023-03-09 15:32:28
hdu 3400 Line belt 三分法

思路:要求最短时间从A到D,则走的路线一定是AB上的一段,CD上的一段,AB与CD之间的一段。

那么可以先三分得到AB上的一个点,在由这个点三分CD!!

代码如下:

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<vector>
#define ll __int64
#define pi acos(-1.0)
using namespace std;
double P,Q,R,ab,cd;
struct point
{
double x,y;
}an[],pp,qq;
int n;
double dis(point &a,point &b)
{
return sqrt(1e-+(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));//注意这里要加上1e-5
}
double cal2(double t)
{
qq.x=an[].x+(an[].x-an[].x)/cd*t*Q;
qq.y=an[].y+(an[].y-an[].y)/cd*t*Q;
return dis(pp,qq)/R+t;
}
double cal(double t)
{
double l,r,mid,mmid,ans;
pp.x=an[].x+(an[].x-an[].x)/ab*t*P;
pp.y=an[].y+(an[].y-an[].y)/ab*t*P;
l=0.0;r=cd/Q;
while((1e-+l)<r){
mid=(r+l)/;
mmid=(mid+r)/;
ans=cal2(mid);
if((ans+1e-)<cal2(mmid))
r=mmid;
else l=mid;
}
return ans+t;
}
int main(){
int t,i;
double l,r,mid,mmid,ans;
cin>>t;
while(t--){
for(i=;i<;i++)
cin>>an[i].x>>an[i].y;
cin>>P>>Q>>R;
ab=dis(an[],an[]);
cd=dis(an[],an[]);
l=0.0;r=ab/P;
while((1e-+l)<r){
mid=(r+l)/;
mmid=(mid+r)/;
ans=cal(mid);
if((ans+1e-)<cal(mmid))
r=mmid;
else l=mid;
}
printf("%.2lf\n",ans);
}
return ;
}