Joint Jog Jam

Interview

Time limit1sMemory limit1024 MB

Summary

Both runners move at constant speed along straight lines from their start points to their end points; find the maximum distance between them over the run.

Level: Medium5 of 10
Topics: Geometry, Math, Implementation, Binary search
Solved: No attempts yet

Problem

Like so many good stories, this one begins with a claim that Kari is a faster runner than Ola, who of course challenges Kari to a run-down.

Dubbed (rather ironically) Non-Competitive Pace Challenge,

they want to see who can run the furthest in a certain amount of time $t$ . Clearly they both choose to run in straight lines with constant speed.

Kari wrote an app to make sure that Ola does not cheat, but the app requires that their phones constantly communicate over Bluetooth.

After their run, Kari needs to ensure that they were never too far apart from each other at any time during the run. Write a program that computes the maximum distance between Kari and Ola at any point during the run.

Input

The input consists of a single line containing eight integers describing four points:

the starting position of Kari,
the starting position of Ola,
the ending position of Kari, and
the ending position of Ola,

in that order. Each point is given by two integers $x$ and $y$ ( $0 \le x, y \le 10^4$ ), the coordinates of the point.

Output

Output the maximum distance between Kari and Ola during their run, with an absolute or relative error of at most $10^{-6}$ .

Examples3

Example 1
Input
```
0 0 0 0 1 1 2 2
```
Expected output
```
1.4142135624
```
Example 2
Input
```
0 0 0 1 0 2 2 1
```
Expected output
```
2.2360679775
```
Example 3
Input
```
5 0 10 0 5 0 10 0
```
Expected output
```
5
```