BNU 51638 Air Hockey 三分二分法
Air Hockey
无聊的过河船同学和无聊的胀鱼同学非常喜欢打桌上冰球(其实只是喜欢听球碰撞时的声音)。在无聊的一天,无聊的过河船同学想到了一个无聊的玩法:两人同时将两个球放桌面上,同时击出,然后听两颗球撞在一起时的声音。然而他们都对击球的精确度把握得不是很好,所以这两颗球并不一定能相撞。
现在假设桌面无限大,并且绝对光滑,给出两球的初始位置、半径和运动速度,保证两球初始没有接触。无聊的过河船同学想知道两球能否相撞(接触即认为相撞),如果能,他想知道两球相撞的时间(从两人击球时开始计时),如果不能,他想知道全过程中两球距离的最小值,这里两球距离的定义为两球上任取两个点的距离的最小值,数据保证这种情况下答案不小于。请注意,冰球是个圆柱体,从空中往下看就是一个圆,且在这个问题中,冰球的高度可以忽略不计。
Input
第一行是一个正整数,表示测试数据的组数,
每组测试数据包含两行,
第行包含五个绝对值不大于的整数,表示第个球的初始位置、半径和运动速度。
Output
对于每组测试数据,若两球能相撞,输出两球相撞的时间,否则输出全过程中两球距离的最小值,相对误差不超过即可,
Sample Input
2
0 0 2 1 0
11 0 1 -1 0
0 0 2 1 0
11 5 1 -1 0
Sample Output
4.0000000000
2.0000000000
Hint
对于第一组样例,两球在击球后4.0秒时发生碰撞,
对于第二组样例,两球不发生碰撞,且在击球后5.5秒时两球距离最近,此时距离为2.0。
Source
Author
题解:
两个不同大小的圆柱体向不同的方向以不同速度同时出发,问是否能碰撞,不能的话给出最小距离,能的话给出碰撞的时间。
解题思路:
可以证明两球在运动过程中一定是先靠近再变远或者直接一直变远的,所以可以三分运动时间求两圆圆心的最近距离,如果两圆最近距离(圆心最近距离-两圆半径)小于1e-6(题干说的条件),则可以碰撞,再以0~达到最近点的时间为区间二分求出碰撞时间,否则直接输出两圆圆心最近距离减去两圆半径之和。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+, M = 1e6+, mod = 1e9+, inf = 1e9+;
typedef long long ll;
double x[], y[], r[], vx[], vy[];
inline double s(double a)
{
return a*a;
}
double d(double t)
{
double x0 = x[] + vx[] * t;
double x1 = x[] + vx[] * t;
double y0 = y[] + vy[] * t;
double y1 = y[] + vy[] * t;
return sqrt(s(x1 - x0) + s(y1 - y0)) - r[] - r[];
}
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
scanf("%lf%lf%lf%lf%lf", &x[], &y[], &r[], &vx[], &vy[]);
scanf("%lf%lf%lf%lf%lf", &x[], &y[], &r[], &vx[], &vy[]);
double l = , r = 1e10;
while (r - l>1e-)//先三分找最低点
{
double mid1 = l + (r - l) / , mid2 = r - (r - l) / ;
double ans1 = d(mid1), ans2 = d(mid2);
if (ans1 <= ans2) r = mid2;
else l = mid1;
}
if (d(l)>=1e-)printf("%.10lf\n", d(l));
else//二分找0点
{
l = ;
while (r - l > 1e-)
{
double mid = (r + l) / ;
if (d(mid) > )l = mid;
else r = mid;
}
printf("%.10f\n", l);
}
}
}
最新文章
- 分享一个基于HTML5实现的视频播放器
- 解决Win8无法升级.NET Framework 3.5.1 提示错误0x800F0906
- CentOS编译安装Apache 2.4.x时报错:configure: error: Bundled APR requested but not found at ./srclib/. Download and unpack the corresponding apr and apr-util packages to ./srclib/.
- hdu 1851 尼姆+巴什博弈
- ios 关于[xxx timeIntervalSinceNow]出现EXC_BAD_ACCESS错误的解决办法
- Spring MVC 流程图
- 黄聪:MYSQL5.6缓存性能优化my.ini文件配置方案
- 三款精美的html5及css3的源码插件
- homework-06&;homework-09
- Android硬件加速
- typedef的使用2——定义函数
- nyoj重建二叉树(不真的建立)
- bzoj2658: [Zjoi2012]小蓝的好友(mrx)
- Linq编程101例
- HDU 5266 pog loves szh III (线段树+在线LCA转RMQ)
- Oracle10g任务调度创建步骤
- 防止tab页重复的去请求服务端
- 安卓图表引擎AChartEngine(六) - 框架源码结构图
- 最全最详细:ubuntu16.04下内核编译以及设备驱动程序的编写(针对新手而写)
- Lucene入门学习二
热门文章
- C#Cookie操作类,删除Cookie,给Cookie赋值
- sql server 还原数据库,数据库提示正在还原中的处理办法
- Centos6.6 安装Memcached
- telerik:RadAsyncUpload 使用 时不执行上传事件的解决办法AsyncUpload1_FileUploaded(object sender, FileUploadedEventArgs e)
- 我的web前端自学之路-心得篇:我为什么要学习web前端?
- [Intermediate Algorithm] - Binary Agents
- C# 聚合数据借口发短信的使用
- Oracle中REGEXP_SUBSTR函数
- tomcat映射java目录 sever.xml
- javaee IO流作业02