首页 > 试题广场 >

最短路2

[编程题]最短路2
"夏天的风 正暖暖吹过 穿过头发穿过耳朵..."耳机里在哼着这首温岚的《夏天的风》,我以为我能这样听着歌,喝着可乐,在寝室里开着空调打游戏,安静地度过这个35℃的下午....
"叮..!"手机屏幕突然弹出一则提醒,"您下午6、7节的排球课别忘了哦~"
唔...果然美好的梦总是会被现实打碎,只好穿上运动鞋,顶着炙热的阳光,向体育馆走去。
体育老师是一个微胖的中年大叔,他总喜欢在上课之前让我们玩游戏,大概是达到热身效果吧。
这次,他又定下了奇怪的游戏规则,于是我把它出成了一道题目:
假设排球场是个无限大的网格,即对于任意的整数z,都有x=z和y=z的直线存在,同学A(Ax,Ay)和同学B(Bx,By)站在整点坐标(即Ax,Ay,Bx,By都是整数)上,这个网格里面,还有另外一条直线H,用Px+Qy=R表示,现在A要走到B所在的位置,他只能沿着网格或者H这条线走,且只能在交点处换路。
求A走到B的最短路长度。

输入描述:
输入的第一行包含一个整数T，表示测试组数。
每个测试用例前面都有一个空白行。
每个测试用例由包含整数Ax,Ay,Bx,By和有理数P,Q,R。


输出描述:
对于每个测试用例输出一个数：表示求A走到B的最短路长度,结果保留三位小数。
示例1

输入

2

2 0 -1 1 1.0 1.0 1.0

-2 3 4 -1 1.0 -0.1 0.47

输出

3.414
10.000

备注:
T ≤ 30
|Ax,Ay,Bx,By|≤ 1000
|P,Q|≤25
|R|≤20000 
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

计算几何
上传者：牛客301599号
难度：
0条回答 7浏览

热门推荐

通过挑战的用户

查看代码

相关试题

最短路2

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号