#2084. 定向越野

定向越野

定向越野

题目描述

标题: 定向越野 - Problem - QOJ.ac

#4560. 定向越野

Statistics

The problem was used in the following contests:

定向越野是一项集智力与体力为一体的体育运动,在这项活动中,选手需要从起点出发,在尽可能短的时间内到达指定的地点。

牛牛非常喜爱这项运动,但是他不知道怎么样才能更快到达终点。他听说来参加集训的你智力过人,于是他把定向越野的地图交给了你,希望你帮他解决一些问题。

牛牛给你的地图描述的是一块平地,地图上不仅清楚地标出了起点和终点的坐标,还标有若干个互不相交圆形区域,每个区域表示一个圆形的水域。对于不会游泳的牛牛来说,进入水域是根本不可能的。因此,牛牛的行动路线不能从水域中穿过。牛牛想知道这样的路线长度最小可以是多少。

输入格式

第一行包含四个实数 Sx,Sy,Tx,Ty ,分别表示起点的x,y坐标和终点的x,y坐标。

第二行包含一个整数n,表示水域的个数。

接下来n行,每行3个整数 xi,yi,ri 表示一片水域的圆心的x,y坐标和半径。

保证起点和终点都不在水域的内部或边界上,起点和终点不重合。

输出格式

输出一行,包含一个实数,四舍五入精确到小数点后恰好1位,表示答案。你的输出必须和标准输出完全一样才算正确。

测试数据保证四舍五入后的答案和准确答案的差的绝对值不大于 4×10−2。

(如果你不知道什么是浮点误差,这段话可以理解为:对于大多数的算法,你可以正常地使用浮点数类型而不用对它进行特殊的处理)

样例一

input

2 1 20 11
2
5 5 4
16 9 4

output

23.0

explanation

这个地图如下图,其中画出的路径即是所求的最短路径。

样例二

见下发文件。

限制与约定

对于所有数据满足,0≤n≤500,−1000≤xi,yi,ri,Sx,Sy,Tx,Ty≤1000 。

测试点n半径相同网格1≤0××2≤1××3≤1××4≤2√×5≤2××6≤3××7≤4√√8≤5××9≤8××10≤16√√11≤20××12≤50√×13≤100√√14≤200××15≤400√√16≤400√√17≤500××18≤500××19≤500××20≤500××

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

2 1 20 11
2
5 5 4
16 9 4
23.0

样例 2

-333 -794 -882 145
70
-39 96 54
84 868 64
-943 -961 169
512 987 128
-782 947 90
525 -373 87
816 -635 66
-881 -411 36
-427 61 47
231 -300 106
-114 -899 114
151 949 41
408 -515 96
-139 838 60
725 -718 49
558 -994 186
787 309 102
973 -258 1
-881 -351 24
-356 726 184
710 925 79
-614 -197 99
-132 75 41
637 632 60
-16 -689 117
-742 -350 100
-512 324 63
-877 -495 48
-487 -820 67
800 155 25
530 743 94
33 -285 92
217 758 108
83 -829 48
638 511 61
-495 117 41
351 -108 106
941 -344 90
-13 -81 103
831 192 23
619 -47 91
669 143 12
-90 348 188
972 -252 5
-620 365 52
-42 753 68
685 -802 44
700 177 34
259 74 85
477 457 108
357 675 12
-392 -577 45
-602 897 96
399 680 30
717 763 83
-627 -874 83
-290 -357 82
-151 -14 50
-151 -259 73
187 -58 65
-287 -200 75
782 15 83
-464 -352 92
-410 -671 50
137 -757 42
325 683 20
926 -541 78
649 140 8
-605 107 69
-89 614 78
1101.8