[SCOI2010]传送带 三分法

时间:2022-09-24 22:25:23

[SCOI2010]传送带

LG传送门

三分法模板。

关于为什么可以三分,我选择感性理解,有人证明了,总之我是懒得证了。

假设路径是\(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]传送带 三分法的更多相关文章

  1. 【BZOJ1857】&lbrack;Scoi2010&rsqb;传送带 三分法

    三分套三分,挺神奇的...每次找到,每个传送带的上下两个三等分点,下面那个小,则一定有更优的在中间. #include <iostream> #include <cstdio> ...

  2. P2571 &lbrack;SCOI2010&rsqb;传送带

    P2571 [SCOI2010]传送带 三分套三分. 前提条件:P3382 [模板]三分法 三分,求区间内单峰函数的最大/最小值. 我们把两条线段都跑三分,先ab后cd,求出最小值. 可以直接将二维坐 ...

  3. 【解题报告】洛谷 P2571 &lbrack;SCOI2010&rsqb;传送带

    [解题报告]洛谷 P2571 [SCOI2010]传送带今天无聊,很久没有做过题目了,但是又不想做什么太难的题目,所以就用洛谷随机跳题,跳到了一道题目,感觉好像不是太难. [CSDN链接](https ...

  4. bzoj 1857&colon; &lbrack;Scoi2010&rsqb;传送带 三分

    题目链接 1857: [Scoi2010]传送带 Time Limit: 1 Sec  Memory Limit: 64 MBSubmit: 934  Solved: 501[Submit][Stat ...

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

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

  6. 【BZOJ1857】&lbrack;Scoi2010&rsqb;传送带 三分套三分

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

  7. BZOJ1857 Scoi2010 传送带 【三分】

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

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

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

  9. BZOJ 1857&colon; &lbrack;Scoi2010&rsqb;传送带

    二次联通门 : BZOJ 1857: [Scoi2010]传送带 /* BZOJ 1857: [Scoi2010]传送带 三分套三分 可能是吧..dalao们都说明显是一个单峰函数 可是我证不出来.. ...

随机推荐

  1. 在 SAE 上部署 ThinkPHP 5&period;0 RC4

    缘起 SAE 和其他的平台有些不同,不能在服务器上运行 Composer 来安装各种包,必须把源码都提交上去.一般的做法,可能是直接把源码的所有文件复制到目录中,添加到版本库.不过,这样就失去了与上游 ...

  2. angular

  3. jQuery的deferred对象使用详解——实现ajax线性请求数据

    最近遇到一个ajax请求数据的问题 ,就是想要请求3个不同的接口,然后请求完毕后对数据进行操作,主要问题就是不知道这3个请求誰先返回来,或者是在进行操作的时候不能保证数据都已经回来,首先想到能完成的就 ...

  4. 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 ...

  5. Sed简介 &lpar;转&rpar;

    Sed简介 sed 是一种在线编辑器,它一次处理一行内容.处理时,把当前处理的行存储在临时缓冲区中,称为“模式空间”(pattern space),接着用sed命令处理缓冲区中的内容,处理完成后,把缓 ...

  6. linux的 压缩与解压 命令集

    bzip2压缩费时但效果好,而且支持hadoop的hdfs文件切分,gzip不行 bzip2 [-cdz] 文件名 -c :将压缩的过程输出到屏幕 -d :解压缩 -z :压缩 -# :压缩比的参数, ...

  7. Java案例&colon;双色球的实现

    //随机生成双色球号码 //案例:6颗红球(33选1)  1颗蓝球(16选1) 代码实现如下: import java.util.Random; import java.util.Arrays; // ...

  8. WMI设置有线网卡IP地址

    一.通过WMI获取物理适配器序号 NetEnabled: 是否启用了适配器,True为启用,False为禁用;PhysicalAdapter: 适配器是否物理或逻辑适配器,True为物理,False为 ...

  9. Spark MLlib 之 Vector向量深入浅出

    Spark MLlib里面提供了几种基本的数据类型,虽然大部分在调包的时候用不到,但是在自己写算法的时候,还是很需要了解的.MLlib支持单机版本的local vectors向量和martix矩阵,也 ...

  10. &lbrack;2018-12-15&rsqb; Hello World!

    这个blog以后就用来发oi相关的算法与数据结构了 还可能想学习一点web前端的知识和一些与计算机有关的软件和技术 可能有空大概会试试搭建blog以及一些各种软件和c++以外的玩意