【BZOJ1857】[Scoi2010]传送带 三分套三分

时间:2022-09-24 22:24:53

【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

【BZOJ1857】[Scoi2010]传送带 三分套三分的更多相关文章

  1. 2018&period;06&period;30 BZOJ1857&colon; &lbrack;Scoi2010&rsqb;传送带(三分套三分)

    1857: [Scoi2010]传送带 Time Limit: 1 Sec Memory Limit: 64 MB Description 在一个2维平面上有两条传送带,每一条传送带可以看成是一条线段 ...

  2. bzoj1857&colon; &lbrack;Scoi2010&rsqb;传送带--三分套三分

    三分套三分模板 貌似只要是单峰函数就可以用三分求解 #include<stdio.h> #include<string.h> #include<algorithm> ...

  3. BZOJ1857 Scoi2010 传送带 【三分】

    BZOJ1857 Scoi2010 传送带 Description 在一个2维平面上有两条传送带,每一条传送带可以看成是一条线段.两条传送带分别为线段AB和线段CD.lxhgww在AB上的移动速度为P ...

  4. 【BZOJ-1857】传送带 三分套三分

    1857: [Scoi2010]传送带 Time Limit: 1 Sec  Memory Limit: 64 MBSubmit: 1077  Solved: 575[Submit][Status][ ...

  5. Bzoj 1857&colon; &lbrack;Scoi2010&rsqb;传送带&lpar;三分套三分&rpar;

    1857: [Scoi2010]传送带 Time Limit: 1 Sec Memory Limit: 64 MB Description 在一个2维平面上有两条传送带,每一条传送带可以看成是一条线段 ...

  6. &lbrack;luogu2571&rsqb;&lbrack;bzoj1857&rsqb;&lbrack;SCOI2010&rsqb;传送门【三分套三分】

    题目描述 在一个2维平面上有两条传送带,每一条传送带可以看成是一条线段.两条传送带分别为线段AB和线段CD.lxhgww在AB上的移动速度为P,在CD上的移动速度为Q,在平面上的移动速度R.现在lxh ...

  7. 【BZOJ1857】传送带(分治经典:三分套三分)

    点此看题面 大致题意: 一个二维平面上有两条传送带\(AB\)和\(CD\),\(AB\)传送带的移动速度为\(P\),\(CD\)传送带的移动速度为\(Q\),步行速度为\(R\),问你从\(A\) ...

  8. &lbrack;BZOJ1857&rsqb;&lbrack;SCOI2010&rsqb;传送带-&lbrack;三分&rsqb;

    Description 传送门 Solution 三分套三分.代码简单但是证明苦兮兮.. 假如我们在AB上选了一个点G,求到该点到D的最小时间. 图中b与CD垂直.设目前从G到D所耗时间最短的路径为G ...

  9. BZOJ 1857 传送带 &lpar;三分套三分&rpar;

    在一个2维平面上有两条传送带,每一条传送带可以看成是一条线段.两条传送带分别为线段AB和线段CD.lxhgww在AB上的移动速度为P,在CD上的移动速度为Q,在平面上的移动速度R.现在lxhgww想从 ...

随机推荐

  1. Bootstrap3系列:按钮式下拉菜单

    1. 基本实例 把按钮放入 .btn-group 中,加入适当的菜单标签,让按钮触发下拉菜单. 1.1 示例代码 <div class="btn-group"> &lt ...

  2. LeetCode 292&period; Nim Game

    Problem: You are playing the following Nim Game with your friend: There to stones. The one who remov ...

  3. 浅谈Oracle中物理结构&lpar;数据文件等。。。&rpar;与逻辑结构&lpar;表空间等。。。。。&rpar;

    初始Oracle时很难理解其中的物理结构和逻辑结构,不明白内存中和硬盘中文件的区别和联系,我也是初学Oracle,这里就简单的谈谈我我看法. 首先,你需要明白的一点是:数据库的物理结构是由数据库的操作 ...

  4. C&num; winform程序怎么打包成安装项目&lpar;图解&rpar;

    1:新建安装部署项目 打开VS,点击新建项目,选择:其他项目类型->安装与部署->安装向导(安装项目也一样),然后点击确定.(详细见下图) 此主题相关图片如下: 2:安装向导 关闭后打开安 ...

  5. eclipse中tomcat配置&lpar;待完善&rpar;

    tomcat版本:apache-tomcat-6.0.29 项目结构:     一.新建server方式 二.eclipse tomcat plugin方式   tomcat plugin方式必须保证 ...

  6. 2&period;Android Studio系列教程2——基本设置与运行

    原文链接:http://stormzhang.com/devtools/2014/11/28/android-studio-tutorial2/   一.项目结构   二.Android Studio ...

  7. jquery&period;ellipsis&period;js段落超出省略号插件

    为了实现在段落尾部超出文字替换为省略号,自己写的插件,并作了简单的优化. 下面给出脚本演示页面及注释,在此之前介绍一下插件参数 1.lineNum:数字.限制段落的行数 2.english:布尔.英文 ...

  8. 学习Ajax

    1.XHR对象 IE7+.Firefox.Opera.Chrome和Safari都支持原生XMLHttpRequest对象,IE6不支持,只支持ActiveXObject对象,该对象在IE11中已经不 ...

  9. Request实例

    Request常用方法        getRequestURL方法返回客户端发出请求时的完整URL. getRequestURI方法返回请求行中的资源名部分. getQueryString 方法返回 ...

  10. mysql连接状态

    mysql连接状态 mysqladmin -uroot -h127.0.0.1 status mysqladmin -uroot -h127.0.0.1 processlist