【BZOJ1857】[Scoi2010]传送带
Description
Input
Output
Sample Input
100 0 100 100
2 2 1
Sample Output
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]传送带 三分套三分的更多相关文章
-
2018.06.30 BZOJ1857: [Scoi2010]传送带(三分套三分)
1857: [Scoi2010]传送带 Time Limit: 1 Sec Memory Limit: 64 MB Description 在一个2维平面上有两条传送带,每一条传送带可以看成是一条线段 ...
-
bzoj1857: [Scoi2010]传送带--三分套三分
三分套三分模板 貌似只要是单峰函数就可以用三分求解 #include<stdio.h> #include<string.h> #include<algorithm> ...
-
BZOJ1857 Scoi2010 传送带 【三分】
BZOJ1857 Scoi2010 传送带 Description 在一个2维平面上有两条传送带,每一条传送带可以看成是一条线段.两条传送带分别为线段AB和线段CD.lxhgww在AB上的移动速度为P ...
-
【BZOJ-1857】传送带 三分套三分
1857: [Scoi2010]传送带 Time Limit: 1 Sec Memory Limit: 64 MBSubmit: 1077 Solved: 575[Submit][Status][ ...
-
Bzoj 1857: [Scoi2010]传送带(三分套三分)
1857: [Scoi2010]传送带 Time Limit: 1 Sec Memory Limit: 64 MB Description 在一个2维平面上有两条传送带,每一条传送带可以看成是一条线段 ...
-
[luogu2571][bzoj1857][SCOI2010]传送门【三分套三分】
题目描述 在一个2维平面上有两条传送带,每一条传送带可以看成是一条线段.两条传送带分别为线段AB和线段CD.lxhgww在AB上的移动速度为P,在CD上的移动速度为Q,在平面上的移动速度R.现在lxh ...
-
【BZOJ1857】传送带(分治经典:三分套三分)
点此看题面 大致题意: 一个二维平面上有两条传送带\(AB\)和\(CD\),\(AB\)传送带的移动速度为\(P\),\(CD\)传送带的移动速度为\(Q\),步行速度为\(R\),问你从\(A\) ...
-
[BZOJ1857][SCOI2010]传送带-[三分]
Description 传送门 Solution 三分套三分.代码简单但是证明苦兮兮.. 假如我们在AB上选了一个点G,求到该点到D的最小时间. 图中b与CD垂直.设目前从G到D所耗时间最短的路径为G ...
-
BZOJ 1857 传送带 (三分套三分)
在一个2维平面上有两条传送带,每一条传送带可以看成是一条线段.两条传送带分别为线段AB和线段CD.lxhgww在AB上的移动速度为P,在CD上的移动速度为Q,在平面上的移动速度R.现在lxhgww想从 ...
随机推荐
-
Bootstrap3系列:按钮式下拉菜单
1. 基本实例 把按钮放入 .btn-group 中,加入适当的菜单标签,让按钮触发下拉菜单. 1.1 示例代码 <div class="btn-group"> < ...
-
LeetCode 292. Nim Game
Problem: You are playing the following Nim Game with your friend: There to stones. The one who remov ...
-
浅谈Oracle中物理结构(数据文件等。。。)与逻辑结构(表空间等。。。。。)
初始Oracle时很难理解其中的物理结构和逻辑结构,不明白内存中和硬盘中文件的区别和联系,我也是初学Oracle,这里就简单的谈谈我我看法. 首先,你需要明白的一点是:数据库的物理结构是由数据库的操作 ...
-
C# winform程序怎么打包成安装项目(图解)
1:新建安装部署项目 打开VS,点击新建项目,选择:其他项目类型->安装与部署->安装向导(安装项目也一样),然后点击确定.(详细见下图) 此主题相关图片如下: 2:安装向导 关闭后打开安 ...
-
eclipse中tomcat配置(待完善)
tomcat版本:apache-tomcat-6.0.29 项目结构: 一.新建server方式 二.eclipse tomcat plugin方式 tomcat plugin方式必须保证 ...
-
2.Android Studio系列教程2——基本设置与运行
原文链接:http://stormzhang.com/devtools/2014/11/28/android-studio-tutorial2/ 一.项目结构 二.Android Studio ...
-
jquery.ellipsis.js段落超出省略号插件
为了实现在段落尾部超出文字替换为省略号,自己写的插件,并作了简单的优化. 下面给出脚本演示页面及注释,在此之前介绍一下插件参数 1.lineNum:数字.限制段落的行数 2.english:布尔.英文 ...
-
学习Ajax
1.XHR对象 IE7+.Firefox.Opera.Chrome和Safari都支持原生XMLHttpRequest对象,IE6不支持,只支持ActiveXObject对象,该对象在IE11中已经不 ...
-
Request实例
Request常用方法 getRequestURL方法返回客户端发出请求时的完整URL. getRequestURI方法返回请求行中的资源名部分. getQueryString 方法返回 ...
-
mysql连接状态
mysql连接状态 mysqladmin -uroot -h127.0.0.1 status mysqladmin -uroot -h127.0.0.1 processlist