[SCOI2010]传送带
三分法模板。
关于为什么可以三分,我选择感性理解,有人证明了,总之我是懒得证了。
假设路径是\(A \to E \to F \to D\),\(E\)和\(F\)分别是从\(AB\)到平面上的拐角和从平面上到\(CD\)上的拐角。首先三分\(E\)的位置,在此基础上三分\(F\)的位置就可以了。
#include<cstdio>
#include<cmath>
#define I inline
#define D double
using namespace std;
const D eps=1e-6;
struct N{D x,y;}a,b,c,d;
D P,Q,R;
I D pwr(D x){return x*x;}
I D dst(N a,N b){return sqrt(pwr(a.x-b.x)+pwr(a.y-b.y));}
D dac0(N f){
N l=c,r=d,p,q;
D u,v,o,e;
while(dst(l,r)>eps)
u=(r.x-l.x)/3,v=(r.y-l.y)/3,p=(N){l.x+u,l.y+v},q=(N){r.x-u,r.y-v},o=dst(f,p)/R+dst(p,d)/Q,e=dst(f,q)/R+dst(q,d)/Q,e-o>eps?r=q:l=p;
return dst(f,l)/R+dst(l,d)/Q;
}
D dac(){
N l=a,r=b,p,q;
D u,v,o,e;
while(dst(l,r)>eps)
u=(r.x-l.x)/3,v=(r.y-l.y)/3,p=(N){l.x+u,l.y+v},q=(N){r.x-u,r.y-v},o=dst(a,p)/P+dac0(p),e=dst(a,q)/P+dac0(q),e-o>eps?r=q:l=p;
return dac0(l)+dst(a,l)/P;
}
int main(){
scanf("%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y,&c.x,&c.y,&d.x,&d.y,&P,&Q,&R);
printf("%.2lf",dac());
return 0;
}
[SCOI2010]传送带 三分法的更多相关文章
-
【BZOJ1857】[Scoi2010]传送带 三分法
三分套三分,挺神奇的...每次找到,每个传送带的上下两个三等分点,下面那个小,则一定有更优的在中间. #include <iostream> #include <cstdio> ...
-
P2571 [SCOI2010]传送带
P2571 [SCOI2010]传送带 三分套三分. 前提条件:P3382 [模板]三分法 三分,求区间内单峰函数的最大/最小值. 我们把两条线段都跑三分,先ab后cd,求出最小值. 可以直接将二维坐 ...
-
【解题报告】洛谷 P2571 [SCOI2010]传送带
[解题报告]洛谷 P2571 [SCOI2010]传送带今天无聊,很久没有做过题目了,但是又不想做什么太难的题目,所以就用洛谷随机跳题,跳到了一道题目,感觉好像不是太难. [CSDN链接](https ...
-
bzoj 1857: [Scoi2010]传送带 三分
题目链接 1857: [Scoi2010]传送带 Time Limit: 1 Sec Memory Limit: 64 MBSubmit: 934 Solved: 501[Submit][Stat ...
-
2018.06.30 BZOJ1857: [Scoi2010]传送带(三分套三分)
1857: [Scoi2010]传送带 Time Limit: 1 Sec Memory Limit: 64 MB Description 在一个2维平面上有两条传送带,每一条传送带可以看成是一条线段 ...
-
【BZOJ1857】[Scoi2010]传送带 三分套三分
[BZOJ1857][Scoi2010]传送带 Description 在一个2维平面上有两条传送带,每一条传送带可以看成是一条线段.两条传送带分别为线段AB和线段CD.lxhgww在AB上的移动速度 ...
-
BZOJ1857 Scoi2010 传送带 【三分】
BZOJ1857 Scoi2010 传送带 Description 在一个2维平面上有两条传送带,每一条传送带可以看成是一条线段.两条传送带分别为线段AB和线段CD.lxhgww在AB上的移动速度为P ...
-
Bzoj 1857: [Scoi2010]传送带(三分套三分)
1857: [Scoi2010]传送带 Time Limit: 1 Sec Memory Limit: 64 MB Description 在一个2维平面上有两条传送带,每一条传送带可以看成是一条线段 ...
-
BZOJ 1857: [Scoi2010]传送带
二次联通门 : BZOJ 1857: [Scoi2010]传送带 /* BZOJ 1857: [Scoi2010]传送带 三分套三分 可能是吧..dalao们都说明显是一个单峰函数 可是我证不出来.. ...
随机推荐
-
在 SAE 上部署 ThinkPHP 5.0 RC4
缘起 SAE 和其他的平台有些不同,不能在服务器上运行 Composer 来安装各种包,必须把源码都提交上去.一般的做法,可能是直接把源码的所有文件复制到目录中,添加到版本库.不过,这样就失去了与上游 ...
- angular
-
jQuery的deferred对象使用详解——实现ajax线性请求数据
最近遇到一个ajax请求数据的问题 ,就是想要请求3个不同的接口,然后请求完毕后对数据进行操作,主要问题就是不知道这3个请求誰先返回来,或者是在进行操作的时候不能保证数据都已经回来,首先想到能完成的就 ...
-
More on Conditions - To Compare -Comparing Sequences and Other Types
The conditions used in while and if statements can contain any operators, not just comparisons. The ...
-
Sed简介 (转)
Sed简介 sed 是一种在线编辑器,它一次处理一行内容.处理时,把当前处理的行存储在临时缓冲区中,称为“模式空间”(pattern space),接着用sed命令处理缓冲区中的内容,处理完成后,把缓 ...
-
linux的 压缩与解压 命令集
bzip2压缩费时但效果好,而且支持hadoop的hdfs文件切分,gzip不行 bzip2 [-cdz] 文件名 -c :将压缩的过程输出到屏幕 -d :解压缩 -z :压缩 -# :压缩比的参数, ...
-
Java案例:双色球的实现
//随机生成双色球号码 //案例:6颗红球(33选1) 1颗蓝球(16选1) 代码实现如下: import java.util.Random; import java.util.Arrays; // ...
-
WMI设置有线网卡IP地址
一.通过WMI获取物理适配器序号 NetEnabled: 是否启用了适配器,True为启用,False为禁用;PhysicalAdapter: 适配器是否物理或逻辑适配器,True为物理,False为 ...
-
Spark MLlib 之 Vector向量深入浅出
Spark MLlib里面提供了几种基本的数据类型,虽然大部分在调包的时候用不到,但是在自己写算法的时候,还是很需要了解的.MLlib支持单机版本的local vectors向量和martix矩阵,也 ...
-
[2018-12-15] Hello World!
这个blog以后就用来发oi相关的算法与数据结构了 还可能想学习一点web前端的知识和一些与计算机有关的软件和技术 可能有空大概会试试搭建blog以及一些各种软件和c++以外的玩意