Humanity's Last Code Exam / 2023_D / Carl’s Vacation

Carl the ant is back! After traversing meandering paths (Problem A, 2004 World Finals) and wandering over octahedrons (Problem C, 2009 World Finals), it is time for a little vacation—time to see the sights! And where better to see the sights than at the tips of tall structures like, say, pyramids!! And where better to see tall pyramids but Egypt!!! (This is so exciting!!!!!)

After taking in the view from the tip of one pyramid, Carl would like to go to the tip of another. Since ants do not do particularly well in the hot sun, he wants to find the minimum distance to travel between the tips of these two pyramids, assuming he can only walk on the surfaces of the pyramids and the plane which the pyramids sit upon. The pyramids are, geometrically, right square pyramids, meaning the apex of the pyramid lies directly above the center of a square base.

**Input**

The first line of input contains five integers x₁,y₁,x₂,y₂,h where −10⁵≤x₁,x₂,y₁,y₂≤10⁵ and (x₁,y₁)≠(x₂,y₂) define an edge of the first pyramid, with the body of the pyramid lying to the left of the directed vector from (x₁,y₁) to (x₂,y₂), and h (1≤h≤10⁵) is the height of the pyramid.

The second line of input describes the second pyramid in the same format. The intersection of the bases of the two pyramids has 0 area.

**Output**

Output the minimum distance Carl travels between the tips of the two pyramids. Your answer should have an absolute or relative error of at most 10^(−6).

**Sample Input 1**

Carl the ant is back! After traversing meandering paths (Problem A, 2004 World Finals) and wandering over octahedrons (Problem C, 2009 World Finals), it is time for a little vacation—time to see the sights! And where better to see the sights than at the tips of tall structures like, say, pyramids!! And where better to see tall pyramids but Egypt!!! (This is so exciting!!!!!)

After taking in the view from the tip of one pyramid, Carl would like to go to the tip of another. Since ants do not do particularly well in the hot sun, he wants to find the minimum distance to travel between the tips of these two pyramids, assuming he can only walk on the surfaces of the pyramids and the plane which the pyramids sit upon. The pyramids are, geometrically, right square pyramids, meaning the apex of the pyramid lies directly above the center of a square base.

**Input**

The first line of input contains five integers \(x_1, y_1, x_2, y_2, h\) where \(-10^5 \leq x_1, x_2, y_1, y_2 \leq 10^5\) and \((x_1, y_1) \neq (x_2, y_2)\) define an edge of the first pyramid, with the body of the pyramid lying to the left of the directed vector from \((x_1, y_1)\) to \((x_2, y_2)\), and \(h\) \((1 \leq h \leq 10^5)\) is the height of the pyramid.

The second line of input describes the second pyramid in the same format. The intersection of the bases of the two pyramids has 0 area.

**Output**

Output the minimum distance Carl travels between the tips of the two pyramids. Your answer should have an absolute or relative error of at most \(10^{-6}\).

**Sample Input 1**