Codeforces 8D Two Friends 三分+二分+计算几何
计算 Codeforces 二分 two 几何 三分
2023-09-11 14:20:44 时间
题目链接:点击打开链接
题意:点击打开链接
三分house到shop的距离,二分这条斜边到cinema的距离
#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> #include<math.h> #include<set> #include<queue> #include<vector> #include<map> using namespace std; #define ll int #define N 90 #define Pi 3.1415926535898 #define eps 1e-10 double t1, t2; struct node{ double x,y; }c,h,s; double dist(double x1,double y1,double x2,double y2){ return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); } double dist(node a,node b){ return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } double work(double du){ node x = {s.x*(1-du) + h.x*du, s.y*(1-du)+h.y*du}; double ac = dist(x,c), as = dist(x,s), ah = dist(x,h); if(ac+ah<=t2&&ac+as<=t1)return min(t2-ah,t1-as); double l = 0, r = 1.0; for(int i = 1; i <= 300 ; i++){ double mid = (l+r)/2; node b = {c.x*(1-mid)+x.x*mid,c.y*(1-mid)+x.y*mid}; double bc = dist(b,c), bs = dist(b, s), bh = dist(b, h); if(bc+bh<=t2 && bc+bs<=t1) l = mid; else r = mid; } node b = {c.x*(1-l)+x.x*l, c.y*(1-l)+x.y*l}; return dist(b,c); } int main(){ ll i, j, u, v; while(cin>>t1>>t2){ cin>>c.x>>c.y; cin>>h.x>>h.y; cin>>s.x>>s.y; double a = dist(c,s), b = dist(c,h), c = dist(h,s); if(b+t2>=a+c){printf("%.8lf\n",min(a+t1+c,b+t2));continue;} t1+=a+eps; t2+=b+eps; double l = 0, r = 1.0, ans = 0; for(i = 1; i <= 300; i++){ double mid1 = (l+r)/2.0, mid2 = (mid1+r)/2.0; double ans1 = work(mid1), ans2 = work(mid2); if(ans1<ans2) l = mid1; else r = mid2; ans = max(ans, max(ans1,ans2)); } printf("%.8lf\n",ans); } return 0; }
相关文章
- AOE网的关键路径的计算
- 异步请求积压可视化|如何 1 分钟内快速定位函数计算积压问题
- 阿里巴巴云原生,在许诺云计算一个什么样的未来?
- qt DateTime 计算时间
- 【python cookbook】【数据结构与算法】8.与字典有关的计算问题
- 物联网、云计算、大数据、人工智能怎么区分,又有何关系
- 通过类继承计算梯形面积
- 【基础入门题035】计算Pi值(一)
- 【原创】开源Math.NET基础数学类库使用(16)C#计算矩阵秩
- 解答私信@m0_64728212 //C 定义一个结构体变量(包括年、月、日)。计算该日在本年中是第几天,注意闰年问题。例如输入2008,8, 8,应输出是2008年中的第221天。
- 例3.2 计算存款利息。有1000元,想存一年。有3种方法可选:。。。
- 一个基于特征向量的近似网页去重算法——term用SVM人工提取训练,基于term的特征向量,倒排索引查询相似文档,同时利用cos计算相似度
- Pytorch总结九之深度学习计算(2)自定义层、读取和存储、GPU计算
- 软考之运筹学计算-车床问题