XMU 1125 越野车大赛 【三分】
1125: 越野车大赛
Time Limit: 500 MS Memory Limit: 64 MB Special Judge
Submit: 8 Solved: 4
[Submit][Status][Web Board]Description
TheBeet正在参加一场越野车大赛。比赛的场地如右图:
共分三块,每一块地面的长宽均为N与M,但地表情况不同,越野车在这段路面上的最高速度也不同。
蓝色线表示TheBeet可能的行车路线。
比赛的要求是要求选手从比赛的场地左上角驾车至右下角。TheBeet想知道如果他在所有路段都以最快速度行驶(不考虑加速阶段),最快能在多少时间内完成比赛。Input
输入数据的第一行为两个正整数N M(N<=3000,M<=1000),表示一块路面的长和宽。
第二行为三个正整数S1,S2,S3(0<S1,S2,S3<=100),从上至下依次表示各个路面上越野车的最高速度。Output
输出一个实数表示TheBeet最快能在多少时间内完成比赛。请输出一个尽可能精确的数字,控制误差在±0.000001的内。
Sample Input
30 10
2 5 3Sample Output
13.7427361525
HINT
如果你的输出和结果的相差在0.000001之内,则认为是正确答案。
Source
题目链接:
http://acm.xmu.edu.cn/JudgeOnline/problem.php?id=1125
题目大意:
比赛地分三块,每一块地面的长宽均为N与M,在1 2 3号地上的速度为S1,S2,S3。
问从左上角到右下角的最小耗时。
题目思路:
【三分】
假设第一段到i,第二段到j,则t=sqrt(1.0*sqr(i)+sqr(m))/s1+sqrt(1.0*sqr(j-i)+sqr(m))/s2+sqrt(sqr(n-j)+sqr(m))/s3
易知t为i,j的函数,且单调。所以两层三分答案。
设区间l,r,取三等分点x1,x2的函数值f1,f2比较,若f1优则r=x2,否则l=x1
直到区间间隔小于EPS停止。
此时即为答案。
/**************************************************** Author : Coolxxx
Copyright 2017 by Coolxxx. All rights reserved.
BLOG : http://blog.csdn.net/u010568270 ****************************************************/
#include<bits/stdc++.h>
#pragma comment(linker,"/STACK:1024000000,1024000000")
#define abs(a) ((a)>0?(a):(-(a)))
#define lowbit(a) (a&(-a))
#define sqr(a) ((a)*(a))
#define mem(a,b) memset(a,b,sizeof(a))
const double EPS=1e-;
const int J=;
const int MOD=;
const int MAX=0x7f7f7f7f;
const double PI=3.14159265358979323;
const int N=;
using namespace std;
typedef long long LL;
double anss;
LL aans;
int cas,cass;
int n,m,lll,ans;
double s1,s2,s3;
inline double cal(double i,double j)
{
return sqrt(1.0*sqr(i)+sqr(m))/s1+sqrt(1.0*sqr(j-i)+sqr(m))/s2+sqrt(sqr(n-j)+sqr(m))/s3;
}
int main()
{
#ifndef ONLINE_JUDGE
// freopen("1.txt","r",stdin);
// freopen("2.txt","w",stdout);
#endif
int i,j,k,l;
int x,y,z;
// for(scanf("%d",&cass);cass;cass--)
// for(scanf("%d",&cas),cass=1;cass<=cas;cass++)
// while(~scanf("%s",s))
while(~scanf("%d",&n))
{
scanf("%d",&m);
scanf("%lf%lf%lf",&s1,&s2,&s3);
double xl,xr,yl,yr,x1,x2,y1,y2,f1,f2;
anss=1e20;
xl=;xr=n;
while(xr-xl>EPS)
{
x1=(xl+xl+xr)/3.0;
x2=(xl+xr+xr)/3.0;
yl=x1;
yr=n;
while(yr-yl>EPS)
{
y1=(yl+yl+yr)/3.0;
y2=(yl+yr+yr)/3.0;
f1=cal(x1,y1);
f2=cal(x1,y2);
if(f1<f2)
yr=y2;
else yl=y1;
}
anss=f1; yl=x2;
yr=n;
while(yr-yl>EPS)
{
y1=(yl+yl+yr)/3.0;
y2=(yl+yr+yr)/3.0;
f1=cal(x2,y1);
f2=cal(x2,y2);
if(f1<f2)
yr=y2;
else yl=y1;
}
f1=anss;
if(f1<f2)
xr=x2;
else xl=x1;
}
printf("%.10lf\n",anss);
}
return ;
}
/*
// //
*/
最新文章
- Flume_常见的几个问题
- Android安全开发之通用签名风险
- javaweb+SSH实现简单的权限管理系统
- 第一零五天上课 PHP TP框架下分页
- 《Web 开发基础》专题系列
- hust 1010 最短循环节点
- EasyUI datagrid frozencolumn的bug???
- [Everyday Mathematics]20150219
- iOS开发——app审核指导方针(官网)
- Sumdiv(各种数学)
- Cisco CatOS系统交换机的SPAN配置
- Cache 大致原理
- Extjs的学习及MIS系统实践应用
- [SDOI 2015]约数个数和
- Sending forms through JavaScript
- 去中心化存储项目终极指南 | Filecoin, Storj 和 PPIO 项目技术对比(下)
- scons, cmake, bazel
- function &;w(){}
- HTML5-CSS3-JavaScript(3)
- ZJOI2018酱油记