把a,d这两个起点和终点之间的中间点三分出来。
其他没什么。
/*
两次三分
题意:给定abcd四个点(包括速度,位置),从a到d,求最短时间。
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
using namespace std;
const int maxn = 105;
const double eps = 1e-8;
const double pi = acos(-1.0);
struct Point {
double x,y;
};
Point a,b,c,d;
double P,Q,R,ans1,ans2;
double dis( Point aa,Point bb ){
return sqrt( (aa.x-bb.x)*(aa.x-bb.x)+(aa.y-bb.y)*(aa.y-bb.y) );
}
double GetAns( double tt1,double tt2 ){
double ans;
Point temp1,temp2;
temp1.x = a.x+tt1*(b.x-a.x),temp1.y = a.y+tt1*(b.y-a.y);
temp2.x = c.x+tt2*(d.x-c.x),temp2.y = c.y+tt2*(d.y-c.y);
ans = dis( a,temp1 )/P+dis( temp1,temp2 )/R+dis( temp2,d )/Q;
return ans;
}
double solve( double x ){
double L,R,mid1,mid2;
L = 0;
R = 1;
while( R-L>eps ){
mid1 = (L+R)/2.0;
mid2 = (mid1+R)/2.0;
if( GetAns( x,mid1 )<GetAns( x,mid2 ) ){
ans2 = mid1;
R = mid2;
}
else{
ans2 = mid2;
L = mid1;
}
}
return GetAns( x,ans2 );
}
int main(){
int T;
scanf("%d",&T);
while( T-- ){
scanf("%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y);
scanf("%lf%lf%lf%lf",&c.x,&c.y,&d.x,&d.y);
scanf("%lf%lf%lf",&P,&Q,&R);
double L,R,mid1,mid2;
L = 0;
R = 1;
while( R-L>eps ){
mid1 = (L+R)/2.0;
mid2 = (mid1+R)/2.0;
if( solve( mid1 )<solve( mid2 ) ){
ans1 = mid1;
R = mid2;
}
else{
ans1 = mid2;
L = mid1;
}
}
printf("%.2lf\n",GetAns( ans1,ans2 ));
}
return 0;
}
分享到:
相关推荐
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
2、new做两件事,一是分配内存,二是调用类的构造函数 3、new建立的是一个对象,而malloc分配的是一块内存 4、new/delete是保留字,不需要头文
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
ACM题库,一些题目和答案,以及解题报告,传上来共享
杭电OnlineJudge 200-2099的解题报告
HDU图论题目分类
acm入门训练和日常训练 对于初学者以及acm爱好者有叫大帮助
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu题目分类
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
其中有pku、hdu、zoj等各大oj的题目分类,pku的oj比较详细一点,按不同算法进行分类,均系从网上自行搜集的。
hdu 1695 GCD(欧拉函数+容斥原理).docx
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu2101AC代码