Drone Navigation: Minimum Energy Calculation

You are given the task of computing the minimum energy required for a drone to navigate through a series of waypoints in 3D space while avoiding obstacles. The energy consumed is equivalent to the Euclidean distance traveled.

The drone can only travel along line segments connecting the given waypoints. However, a line segment is considered blocked if either endpoint is inside any of the given axis-aligned rectangular boxes (obstacles). In such a case, the segment cannot be used in the path.

You should construct a graph where each waypoint is a node, and an edge exists between two nodes if and only if the line segment between them does not intersect any obstacle. The weight of an edge is the Euclidean distance between the two waypoints, given by the formula:

\( d(p, q) = \sqrt{(p_x - q_x)^2 + (p_y - q_y)^2 + (p_z - q_z)^2} \)

Once the graph is constructed, use Dijkstra's algorithm to determine the shortest path (i.e., the minimum energy consumption) from the start waypoint to the goal waypoint. If no valid path exists, output -1.

The input format ensures that the start and goal waypoints are among the provided list of waypoints.

inputFormat

The input is read from standard input (stdin) and has the following format:

n m
x1 y1 z1
x2 y2 z2
... (n lines of waypoints)
ox1 oy1 oz1 ox2 oy2 oz2
... (m lines of obstacles)
start_x start_y start_z
goal_x goal_y goal_z

Here,

• n is the number of waypoints.
• m is the number of obstacles.
• Each waypoint is represented by three numbers (its x, y, z coordinates).
• Each obstacle is an axis-aligned rectangular box defined by six numbers representing the minimum and maximum x, y, z coordinates, respectively.
• The last two lines represent the start and goal waypoints, which are guaranteed to be among the waypoints.

outputFormat

The output is a single line printed to standard output (stdout). It should be the minimum energy required to reach from the start to the goal formatted to 5 decimal places. If the goal is unreachable, output -1.

## sample

4 2
0 0 0
5 5 5
10 10 10
15 15 15
2 2 2 7 7 7
12 12 12 17 17 17
0 0 0
15 15 15

-1