【BZOJ1857】[Scoi2010]传送带

Description

在一个2维平面上有两条传送带,每一条传送带可以看成是一条线段。两条传送带分别为线段AB和线段CD。lxhgww在AB上的移动速度为P,在CD上的移动速度为Q,在平面上的移动速度R。现在lxhgww想从A点走到D点,他想知道最少需要走多长时间

Input

输入数据第一行是4个整数,表示A和B的坐标,分别为Ax,Ay,Bx,By 第二行是4个整数,表示C和D的坐标,分别为Cx,Cy,Dx,Dy 第三行是3个整数,分别是P,Q,R

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<= Ax,Ay,Bx,By,Cx,Cy,Dx,Dy<=1000
1<=P,Q,R<=10

题解:最终路径一定是先在AB上走x米,然后直线走到CD上,再走y米。那么如果x确定了,最终答案显然是一个关于y的单峰函数,可以直接三分(其实感觉可以O(1)算)。但是x的位置如何确定呢?x的位置也是一个单峰函数!证明不太会,网上有~

所以三分套三分即可。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
struct point
{
double x,y;
point() {}
point(double a,double b) {x=a,y=b;}
point operator + (const point &a) const {return point(x+a.x,y+a.y);}
point operator * (const double &a) const {return point(x*a,y*a);}
}s1,t1,s2,t2;
double P,Q,R,ans;
inline double dis(point a,point b)
{
return sqrt((b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y));
}
inline double calc(point a,point b)
{
double tmp=dis(s1,a)/P+dis(a,b)/R+dis(b,t2)/Q;
ans=min(ans,tmp);
return tmp;
}
double check(point S)
{
point l=s2,r=t2,m1,m2;
for(int i=1;i<=50;i++)
{
m1=(l*(2.0/3))+(r*(1.0/3)),m2=(l*(1.0/3))+(r*(2.0/3));
if(calc(S,m1)<calc(S,m2)) r=m2;
else l=m1;
}
return calc(S,l);
}
int main()
{
scanf("%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf",&s1.x,&s1.y,&t1.x,&t1.y,&s2.x,&s2.y,&t2.x,&t2.y,&P,&Q,&R);
point l=s1,r=t1,m1,m2;
ans=1e10;
for(int i=1;i<=50;i++)
{
m1=(l*(2.0/3))+(r*(1.0/3)),m2=(l*(1.0/3))+(r*(2.0/3));
if(check(m1)<check(m2)) r=m2;
else l=m1;
}
printf("%.2lf",ans);
return 0;
}//0 0 100 0 100 100 0 100 2 2 1

最新文章

  1. synthesize 与dynamic的区别
  2. 《Java疯狂讲义》(第3版)学习笔记 2 - Java语言的运行机制
  3. 纪念逝去的岁月——C/C++二分查找
  4. safenet 超级狗 java调用 小计
  5. Html form 表单提交前验证
  6. sell - 配置service
  7. NAND flash cache编程
  8. 如何通过 OAuth 2.0 使 iOS Apps 集成 LinkedIn 登录功能?
  9. iframe实现面页无刷新提交表单
  10. bzoj1324
  11. HDU 1114 Piggy-Bank(完全背包)
  12. java如何防止反编译
  13. memcached与redis
  14. 在不同版本号hdfs集群之间转移数据
  15. Python 使用心得之--变量命名
  16. [转载] 常用 Java 静态代码分析工具的分析与比较
  17. BZOJ2655calc
  18. 【Spring】Spring bean的实例化
  19. CSS效果:简单的登录框
  20. 详解基于朴素贝叶斯的情感分析及 Python 实现

热门文章

  1. Windows Mobile自动更新
  2. Refresh Tokens: When to Use Them and How They Interact with JWTs
  3. hdu 2066 一个人的旅行(dijkstra)
  4. 修改mysql中的auto_increment
  5. Atitit.软件仪表盘(7)--温度监测子系统--电脑重要部件温度与监控and警报
  6. Android Studio 更新gradle插件
  7. CentOS7 使用tab建补全命令
  8. yii2 beta版 执行流程
  9. Log4j容器深入探究
  10. [uboot]MLO和uboot-spl.bin, uboot.img和uboot.bin