You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

采蘑菇

题目描述

“知了——知了——”

“好热啊——”

又到了一年盛夏时节，所有动物在这个时间段都不想出门，小白兔也一样，但是它今天被妈妈拜托去采蘑菇。

小白兔家所在的草原可以看成一个 $xy$ 平面，其中小白兔家的坐标在$(x_s, y_s)$，蘑菇田的坐标在$(x_t, y_t)$。

小白兔看着正午强烈的阳光正在抱怨的时候，突然发现，这个草原上有一些巨型的圆形蘑菇，它们底下的阴影可以供乘凉用。就是说，草原上有$N$个巨型圆形蘑菇，第$i$个巨型圆形蘑菇在地上形成的阴影以$(x_i, y_i)$为中心，$r_i$为半径。这些蘑菇的阴影也许会互相重叠或互相包含，阴影下面不会被太阳晒到。

因为小白兔很热，所以它想被阳光晒到的路程尽可能少。请求出小白兔在去摘蘑菇的路上被太阳晒到的最短路程。由于阴影可能会动，小白兔希望你能在1s内算出这个结果。

输入格式

输入的第一行包含四个整数$x_s,y_s,x_t,y_t$表示小白兔家和蘑菇田的坐标。第二行一个正整数$N$表示巨型圆形蘑菇的数量，后面$N$行每行三个整数$x_i,y_i,r_i$表示第$i$个巨型蘑菇形成的圆形阴影的圆心$(x_i,y_i)$和半径$r_i$。

输出格式

一个浮点数表示小白兔在去摘蘑菇的路上被太阳晒到的最短路程。保留6位小数输出。

样例 #1

样例输入 #1

-2 2 2 -2
1
0 0 1

样例输出 #1

3.656854

样例 #2

样例输入 #2

0 -2 0 2
2
0 1 2
0 -1 2

样例输出 #2

0.000000

样例 #3

样例输入 #3

4 -2 -2 4
3
0 0 2
4 0 1
0 4 1

样例输出 #3

4.000000

数据范围

对10%的数据，$n=1$

对另外20%的数据，$y_s,y_t,y_i=0,r_i=1$

对100%的数据，$1\le N\le 1000$，$ -10^9\le x_s,\ y_s,\ x_t,\ y_t,\ x_i,\ y_i\le 10^9 $，$(x_s,\ y_s)$ ≠ $(x_t,\ y_t)$，$1\le\ r_i\le\ 10^9$