Return of the Jedi

Time limit1sMemory limit128 MB

Summary

Given up to 10 non-overlapping circular trees in the plane, find the shortest path length around them from start to goal point, then divide by the speed of 200 miles per hour.

Level: Hard8 of 10
Topics: Geometry, Graph, Shortest path, Implementation
Solved: No attempts yet

Problem

Luke Skywalker races through the forest on a speeder bike, trying to outrun a patrol of Imperial scouts on the forest moon of Endor. The moon is covered by dense foliage and a thick forest of ancient, towering trees. The speeder bike is an antigravity vehicle that moves at a constant speed of 200 miles per hour, and Luke wants to reach Princess Leia in the Ewok village as quickly as possible.

Model the forest as a plane containing $T$ trees. Each tree is a circular obstacle, and Luke may not pass through the interior of any tree, so his route must curve around them. Luke starts at $(x_{luke}, y_{luke})$ and the Ewok village is at $(x_{ewok}, y_{ewok})$ . Find the shortest possible travel time from Luke's starting position to the Ewok village.

Input

The first line contains five numbers: the integer $T$ followed by $x_{luke}$ , $y_{luke}$ , $x_{ewok}$ , and $y_{ewok}$ .

Each of the next $T$ lines describes one tree with three numbers: its center $x_{tree}$ , $y_{tree}$ and its diameter $d_{tree}$ .

$T$ is an integer that is at most $10$ . All coordinates and diameters are real numbers measured in miles. No two trees intersect or touch each other, and neither Luke's start nor the Ewok village lies inside a tree.

Output

Print a single real number: the minimum travel time in seconds, rounded to exactly two decimal places.

Examples4

Example 1

Input

2 0.0 0.0 10.0 0.0
4.0 0.0 1.0
6.0 0.0 1.0

Expected output

181.13

Example 2
Input
```
0 0 0 10 0
```
Expected output
```
180.00
```
Example 3
Input
```
0 0 0 3 4
```
Expected output
```
90.00
```
Example 4
Input
```
1 0 0 10 0
5 0 2
```
Expected output
```
183.61
```