bzoj1857 [ SCOI2010 ] -- 三分套三分
2018-06-17 22:34:36来源:未知 阅读 ()
显然我们一定是先走到AB上一点X,然后走到CD上一点Y,最后到D。
那么答案就是|AX|/P+|XY|/R+|YD|/Q
假设我们已经确定了X,那么目标就是在CD上找一点Y,使|XY|/R+|YD|/Q最小。
显然这是个单峰函数。
那么三分套三分就可以了。
代码:
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; #define Eps 1e-3 struct Node{ double x,y; Node(){} Node(double x,double y):x(x),y(y){} Node operator + (Node a){return Node(x+a.x,y+a.y);} Node operator - (Node a){return Node(x-a.x,y-a.y);} Node operator / (double a){return Node(x/a,y/a);} inline void Read(){scanf("%lf%lf",&x,&y);} }a,b,c,d,l,r,m1,m2; int i,j,k,n,m,p,v1,v2,v3; inline double Dis(Node a,Node b){ return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } inline double Get(Node a,Node b,Node c,Node d){ return Dis(a,b)/v1+Dis(b,c)/v3+Dis(c,d)/v2; } inline double Calc(Node x){ Node l=c,r=d,m1,m2; while(Dis(l,r)>Eps){ m1=(r-l)/3;m2=r-m1;m1=l+m1; if(Get(a,x,m1,d)>Get(a,x,m2,d))l=m1;else r=m2; } return Get(a,x,l,d); } int main(){ a.Read();b.Read();c.Read();d.Read(); scanf("%d%d%d",&v1,&v2,&v3); l=a;r=b; while(Dis(l,r)>Eps){ m1=(r-l)/3;m2=r-m1;m1=l+m1; if(Calc(m1)>Calc(m2))l=m1;else r=m2; } printf("%.2lf\n",Calc(l)); return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:分块之区间查询与区间修改
下一篇:分块简介
- BZOJ1853: [Scoi2010]幸运数字(容斥原理) 2018-09-01
- C++系统学习之八:IO库 2018-08-26
- 基础算法 - 二分与三分 - 蒟蒻复习基础 2018-07-18
- BZOJ1854: [Scoi2010]游戏(二分图匹配) 2018-07-09
- bzoj1856 [ SCOI2010 ] -- 卡特兰数 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash