New Game
时间限制: 1 Sec 内存限制: 128 MB Special Judge提交: 157 解决: 53[] [] [] [命题人:]题目描述
Eagle Jump公司正在开发一款新的游戏。泷本一二三作为其员工,获得了提前试玩的机会。现在她正在试图通过一个迷宫。 这个迷宫有一些特点。为了方便描述,我们对这个迷宫建立平面直角坐标系。迷宫中有两条平行直线 L1:Ax+By+C1=0,L2:Ax+By+C2=0,还有 n 个圆 。角色在直线上、圆上、圆内行走不消耗体力。在其他位置上由S点走到T点消耗的体力为S和T的欧几里得距离。 泷本一二三想从L1出发,走到L2。请计算最少需要多少体力。
输入
第一行五个正整数n,A,B,C1,C2(1≤n≤1000,−10000≤A,B,C1,C2≤10000),其中A,B 不同时为 0。 接下来 n 行每行三个整数x,y,r(−10000≤x,y≤10000,1≤r≤10000) 表示一个圆心为 (x,y),半径为 r 的圆。
输出
仅一行一个实数表示答案。与标准答案的绝对误差或者相对误差不超过10 -4即算正确。
样例输入
2 0 1 0 -40 1 11 3 1
样例输出
0.236068
题意
给一些圆和两个平行线,在圆内、圆上和线上走不消耗体力,其它消耗的体力为两点之间的几何距离。
分析
看出来是最短路就很简单了,直接建图跑最短路就可以了。
/// author:Kissheart ///#include#include #include #include #include #include #include #include #include #include #include