Codeforces8DTwoFriends

作者：可乐加冰2502937787 | 来源：互联网 | 2023-09-17 13:38

【题意】有两个人Alan和Bob，他们现在都在A点，现在Bob想去B点，Alan想先到C点再去B点。Alan所走的总路程不能超过T1&#x

【题意】有两个人Alan和Bob&＃xff0c;他们现在都在A点&＃xff0c;现在Bob想去B点&＃xff0c;Alan想先到C点再去B点。Alan所走的总路程不能超过T1&＃xff0c;Bob所走的总路程不能超过T2。求他们从A出发到第一次分开所能走的最长的公共路程。

【解题方法】参考XHR神牛的论文AC。

【AC代码】

// //Created by just_sort 2016/12/8 //Copyright (c) 2016 just_sort.All Rights Reserved //#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using namespace __gnu_pbds; typedef long long LL; typedef pair pp; #define MP(x,y) make_pair(x,y) const int maxn &＃61; 400020; const int maxm &＃61; 1<<12; const int inf &＃61; 0x3f3f3f3f; typedef tree,rb_tree_tag,tree_order_statistics_node_update>order_set; //headtypedef long double LD; const LD eps &＃61; 1e-10;int dcmp(LD x) {if(fabs(x) }LD sqr(LD x) { return x * x; }struct Point {LD x, y;Point(LD x &＃61; 0, LD y &＃61; 0):x(x), y(y) {}void read() { cin >> x >> y; } };Point operator - (const Point& A, const Point& B) {return Point(A.x - B.x, A.y - B.y); }bool operator &＃61;&＃61; (const Point& A, const Point& B) {return dcmp(A.x - B.x) &＃61;&＃61; 0 && dcmp(A.y - B.x) &＃61;&＃61; 0; }LD Dot(const Point& A, const Point& B) {return A.x * B.x &＃43; A.y * B.y; }LD Length(const Point& A) { return sqrt(Dot(A, A)); }LD angle(const Point& A) { return atan2(A.y, A.x); }struct Circle {Point c;LD r;Circle() {}Circle(Point c, LD r):c(c), r(r) {}Point point(LD a) {return Point(c.x &＃43; cos(a) * r, c.y &＃43; sin(a) * r);} };LD t1, t2, T1, T2; Point p[3]; Circle o[3]; vector sol;bool OnCircle(Point p, Circle C) {return dcmp(Length(p - C.c) - C.r) &＃61;&＃61; 0; }bool getCirclesolsection(Circle C1, Circle C2) {LD &r1 &＃61; C1.r, &r2 &＃61; C2.r;LD &x1 &＃61; C1.c.x, &x2 &＃61; C2.c.x, &y1 &＃61; C1.c.y, &y2 &＃61; C2.c.y;LD d &＃61; Length(C1.c - C2.c);if(dcmp(fabs(r1-r2) - d) > 0) return true;if(dcmp(r1 &＃43; r2 - d) <0) return false;LD d2 &＃61; Dot(C1.c - C2.c, C1.c - C2.c);LD a &＃61; r1*(x1-x2)*2, b &＃61; r1*(y1-y2)*2, c &＃61; r2*r2-r1*r1-d*d;LD p &＃61; a*a&＃43;b*b, q &＃61; -a*c*2, r &＃61; c*c-b*b;LD cosa, sina, cosb, sinb;//One solsectionif(dcmp(d - (r1 &＃43; r2)) &＃61;&＃61; 0 || dcmp(d - fabs(r1 - r2)) &＃61;&＃61; 0) {cosa &＃61; -q / p / 2;sina &＃61; sqrt(1 - sqr(cosa));Point p(x1 &＃43; C1.r * cosa, y1 &＃43; C1.r * sina);if(!OnCircle(p, C2)) p.y &＃61; y1 - C1.r * sina;sol.push_back(p);return true;}//Two solsectionsLD delta &＃61; sqrt(q * q - p * r * 4);cosa &＃61; (delta - q) / p / 2;cosb &＃61; (-delta - q) / p / 2;sina &＃61; sqrt(1 - sqr(cosa));sinb &＃61; sqrt(1 - sqr(cosb));Point p1(x1 &＃43; C1.r * cosa, y1 &＃43; C1.r * sina);Point p2(x1 &＃43; C1.r * cosb, y1 &＃43; C1.r * sinb);if(!OnCircle(p1, C2)) p1.y &＃61; y1 - C1.r * sina;if(!OnCircle(p2, C2)) p2.y &＃61; y1 - C1.r * sinb;if(p1 &＃61;&＃61; p2) p1.y &＃61; y1 - C1.r * sina;sol.push_back(p1);sol.push_back(p2);return true; }bool Include(Circle C1, Circle C2) {LD d &＃61; Length(C1.c - C2.c);if(dcmp(fabs(C1.r-C2.r) - d) > 0) return true;return false; }bool InAllCircle(const Point& t) {for(int i &＃61; 0; i <3; i&＃43;&＃43;) {LD d &＃61; Length(t - o[i].c);if(dcmp(d - o[i].r) > 0) return false;}return true; }//判断3个圆是否有交 bool check() {sol.clear();for(int i &＃61; 0; i <3; i&＃43;&＃43;)for(int j &＃61; i &＃43; 1; j <3; j&＃43;&＃43;)if(!getCirclesolsection(o[i], o[j])) return false;for(int i &＃61; 0; i <3; i&＃43;&＃43;)for(int j &＃61; i &＃43; 1; j <3; j&＃43;&＃43;)if(Include(o[i], o[j])) return true;for(Point t : sol)if(InAllCircle(t)) return true;return false; }int main() {cin>>t1>>t2;for(int i &＃61; 0; i <3; i&＃43;&＃43;) p[i].read();LD AB &＃61; Length(p[1] - p[0]);LD AC &＃61; Length(p[2] - p[0]);LD BC &＃61; Length(p[2] - p[1]);T1 &＃61; AC &＃43; BC &＃43; t1;T2 &＃61; AB &＃43; t2;if(dcmp(T2 - AC - BC) >&＃61; 0){LD ans &＃61; min(T1, T2);printf("%.10Lf\n", ans);return 0;}LD l &＃61; 0, r &＃61; min(T1 - BC, T2);for(int i &＃61; 0; i <100; i&＃43;&＃43;){LD mid &＃61; (l &＃43; r) / 2.0;o[0] &＃61; Circle(p[0], mid);o[1] &＃61; Circle(p[1], T2 - mid);o[2] &＃61; Circle(p[2], T1 - BC - mid);if(check()) l &＃61; mid;else r &＃61; mid;}printf("%.10Lf\n", l);return 0; }

推荐阅读

include
二叉树层序创建问题的解决方法

本文介绍了解决二叉树层序创建问题的方法。通过使用队列结构体和二叉树结构体，实现了入队和出队操作，并提供了判断队列是否为空的函数。详细介绍了解决该问题的步骤和流程。 ... [详细]

蜡笔小新 2023-12-13 18:20:50
include
差分约束系统求解House Man跳跃问题的思路与方法

本文讨论了使用差分约束系统求解House Man跳跃问题的思路与方法。给定一组不同高度，要求从最低点跳跃到最高点，每次跳跃的距离不超过D，并且不能改变给定的顺序。通过建立差分约束系统，将问题转化为图的建立和查询距离的问题。文章详细介绍了建立约束条件的方法，并使用SPFA算法判环并输出结果。同时还讨论了建边方向和跳跃顺序的关系。 ... [详细]

蜡笔小新 2023-12-14 11:49:51
include
李逍遥寻找仙药的迷阵之旅

本文讲述了少年李逍遥为了救治婶婶的病情，前往仙灵岛寻找仙药的故事。他需要穿越一个由M×N个方格组成的迷阵，有些方格内有怪物，有些方格是安全的。李逍遥需要避开有怪物的方格，并经过最少的方格，找到仙药。在寻找的过程中，他还会遇到神秘人物。本文提供了一个迷阵样例及李逍遥找到仙药的路线。 ... [详细]

蜡笔小新 2023-12-12 13:59:33
get
JDK源码学习之HashTable(附带面试题)的学习笔记

本文介绍了JDK源码学习之HashTable(附带面试题)的学习笔记，包括HashTable的定义、数据类型、与HashMap的关系和区别。文章提供了干货，并附带了其他相关主题的学习笔记。 ... [详细]

蜡笔小新 2023-12-12 13:05:17
include
Codeforces Round #321 (Div. 2) Kefa and Dishes 状压+spfa

本文介绍了Codeforces Round #321 (Div. 2)比赛中的问题Kefa and Dishes，通过状压和spfa算法解决了这个问题。给定一个有向图，求在不超过m步的情况下，能获得的最大权值和。点不能重复走。文章详细介绍了问题的题意、解题思路和代码实现。 ... [详细]

蜡笔小新 2023-12-11 10:37:34
io
HashMap的相关问题及其底层数据结构和操作流程

本文介绍了关于HashMap的相关问题，包括其底层数据结构、JDK1.7和JDK1.8的差异、红黑树的使用、扩容和树化的条件、退化为链表的情况、索引的计算方法、hashcode和hash()方法的作用、数组容量的选择、Put方法的流程以及并发问题下的操作。文章还提到了扩容死链和数据错乱的问题，并探讨了key的设计要求。对于对Java面试中的HashMap问题感兴趣的读者，本文将为您提供一些有用的技术和经验。 ... [详细]

蜡笔小新 2023-12-10 17:07:36
heap
LeetCode笔记：剑指Offer 41. 数据流中的中位数（Java、堆、优先队列、知识点）

本文介绍了LeetCode剑指Offer 41题的解题思路和代码实现，主要涉及了Java中的优先队列和堆排序的知识点。优先队列是Queue接口的实现，可以对其中的元素进行排序，采用小顶堆的方式进行排序。本文还介绍了Java中queue的offer、poll、add、remove、element、peek等方法的区别和用法。 ... [详细]

蜡笔小新 2023-12-14 13:34:58
io
clone的fork与pthread_create创建线程有何不同

本文讨论了clone的fork与pthread_create创建线程的不同之处。进程是一个指令执行流及其执行环境，其执行环境是一个系统资源的集合。在调用系统调用fork创建一个进程时，子进程只是完全复制父进程的资源，这样得到的子进程独立于父进程，具有良好的并发性。但是二者之间的通讯需要通过专门的通讯机制，另外通过fork创建子进程系统开销很大。因此，在某些情况下，使用clone或pthread_create创建线程可能更加高效。 ... [详细]

蜡笔小新 2023-12-12 20:00:06
io
深入理解Kafka服务端请求队列中请求的处理

本文深入分析了Kafka服务端请求队列中请求的处理过程，详细介绍了请求的封装和放入请求队列的过程，以及处理请求的线程池的创建和容量设置。通过场景分析、图示说明和源码分析，帮助读者更好地理解Kafka服务端的工作原理。 ... [详细]

蜡笔小新 2023-12-12 16:14:59
get
欢乐的票圈重构之旅——RecyclerView的头尾布局增加

项目重构的Git地址：https:github.comrazerdpFriendCircletreemain-dev项目同步更新的文集：http:www.jianshu.comno ... [详细]

蜡笔小新 2023-12-11 19:09:56
get
重入锁（ReentrantLock）学习及实现原理

本文介绍了重入锁（ReentrantLock）的学习及实现原理。在学习synchronized的基础上，重入锁提供了更多的灵活性和功能。文章详细介绍了重入锁的特性、使用方法和实现原理，并提供了类图和测试代码供读者参考。重入锁支持重入和公平与非公平两种实现方式，通过对比和分析，读者可以更好地理解和应用重入锁。 ... [详细]

蜡笔小新 2023-12-11 15:16:28
include
文件压缩解压的哈夫曼树实现

本文介绍了使用哈夫曼树实现文件压缩和解压的方法。首先对数据结构课程设计中的代码进行了分析，包括使用时间调用、常量定义和统计文件中各个字符时相关的结构体。然后讨论了哈夫曼树的实现原理和算法。最后介绍了文件压缩和解压的具体步骤，包括字符统计、构建哈夫曼树、生成编码表、编码和解码过程。通过实例演示了文件压缩和解压的效果。本文的内容对于理解哈夫曼树的实现原理和应用具有一定的参考价值。 ... [详细]

蜡笔小新 2023-12-11 14:13:46
io
Java面经整理及相关概念解析

本文整理了Java面试中常见的问题及相关概念的解析，包括HashMap中为什么重写equals还要重写hashcode、map的分类和常见情况、final关键字的用法、Synchronized和lock的区别、volatile的介绍、Syncronized锁的作用、构造函数和构造函数重载的概念、方法覆盖和方法重载的区别、反射获取和设置对象私有字段的值的方法、通过反射创建对象的方式以及内部类的详解。 ... [详细]

蜡笔小新 2023-12-10 22:17:08
io
深入解析Linux下的I/O多路转接epoll技术

本文深入解析了Linux下的I/O多路转接epoll技术，介绍了select和poll函数的问题，以及epoll函数的设计和优点。同时讲解了epoll函数的使用方法，包括epoll_create和epoll_ctl两个系统调用。 ... [详细]

蜡笔小新 2023-12-10 14:18:30
include
状态压缩算法解决关灯问题2

本文介绍了一道经典的状态压缩题目——关灯问题2，并提供了解决该问题的算法思路。通过使用二进制表示灯的状态，并枚举所有可能的状态，可以求解出最少按按钮的次数，从而将所有灯关掉。本文还对状压和位运算进行了解释，并指出了该方法的适用性和局限性。 ... [详细]

蜡笔小新 2023-12-10 11:23:10

可乐加冰2502937787

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章