[BZOJ1857][Contest1348]传送带
题面
Description
题目描述：
在一个二维平面上有两条传送带，每一条传送带可以看成是一条线段。两条传送带分别为线段AB和线段CD。小y在AB上的移动速度为P，在CD上的移动速度为Q，在平面上的移动速度R。现在，小y想从A点走到D点，请问他最少需要走多长时间。
输入格式：
第一行是4个整数，表示A和B的坐标，分别为Ax，Ay，Bx，By。
第二行是4个整数，表示C和D的坐标，分别为Cx，Cy，Dx，Dy。
第三行是3个整数，分别是P，Q，R。
输出格式：
输出一行一个数，表示小y从A点走到D点的最短时间，保留到小数点后2位。
样例输入：
0 0 0 100
100 0 100 100
2 2 1
样例输出：
136.60
数据范围：
对于30%的数据满足：
1<=Ax,Ay,Bx,By,Cx,Cy,Dx,Dy<=10
1<=P,Q,R<=5
对于100%的数据满足：
1<=Ax,Ay,Bx,By,Cx,Cy,Dx,Dy<=1000
1<=P,Q,R<=10
题意
一个二维平面上有两条线段AB和CD，在AB上行动速度为P，CD上为Q，其他为R，求从A到D最短时间。
题解
可以发现最短路径一定是从A走到AB上的一点，在走到CD上的一点，再走到D。
考虑固定AB上的点，发现CD上的点可以三分得到答案。可是题目并没有固定AB上的点，所以我们要再三分AB上的点（这个不会证）。
所以思路有了：三分套三分。
#include<iostream>
#include<cmath>
using namespace std;
const double eps=1e-9;
int ax,ay,bx,by,cx,cy,dx,dy,p,q,r;
double dis(double x1,double y1,double x2,double y2){
return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
}
double work2(double mx,double my){//三分CD上的点
double lx=cx,ly=cy,rx=dx,ry=dy;
while(dis(lx,ly,rx,ry)>eps){
double x=(rx-lx)/3,y=(ry-ly)/3;
double lmx=lx+x,lmy=ly+y,rmx=rx-x,rmy=ry-y;
double ans1=dis(mx,my,lmx,lmy)/r+dis(dx,dy,lmx,lmy)/q;
double ans2=dis(mx,my,rmx,rmy)/r+dis(dx,dy,rmx,rmy)/q;
if(ans2-ans1>eps)rx=rmx,ry=rmy;
else lx=lmx,ly=lmy;
}
return dis(mx,my,lx,ly)/r+dis(dx,dy,lx,ly)/q;
}
double work1(double lx,double ly,double rx,double ry){//三分AB上的点
while(dis(lx,ly,rx,ry)>eps){
double x=(rx-lx)/3,y=(ry-ly)/3;
double lmx=lx+x,lmy=ly+y,rmx=rx-x,rmy=ry-y;
double ans1=work2(lmx,lmy)+dis(ax,ay,lmx,lmy)/p;
double ans2=work2(rmx,rmy)+dis(ax,ay,rmx,rmy)/p;
if(ans2-ans1>eps)rx=rmx,ry=rmy;
else lx=lmx,ly=lmy;
}
return work2(lx,ly)+dis(ax,ay,lx,ly)/p;
}
int main(){
scanf("%d%d%d%d%d%d%d%d",&ax,&ay,&bx,&by,&cx,&cy,&dx,&dy);
scanf("%d%d%d",&p,&q,&r);
printf("%.2lf",work1(ax,ay,bx,by));
}
优质内容筛选与推荐>>
1、第十一章-CRF的奇妙之处
2、使用ASP.NET/PHP/JSP 或者javascript都会用到http的不同状态，一些常见的状态码为：
3、经常用到的css和html属性
4、Ubuntu无法连接无线网
5、注意ArrayAdapter的Add()方法