hackercupai/hackercup huggingface dataset:
Cole is a programmer in the coal division of Metal (previously Facebulk), working across \(T\) office buildings with very pleasant coworkers and unlimited free ice cream. However, as a self-proclaimed antisocial code monkey, he still prefers to "mine" his own business when possible.

A given office building can be represented by an axis-aligned rectangle with opposite corners \((0, 0)\) and \((X_R, Y_R)\) on a 2D plane. Inside, there are \(N\) friendly coworkers, the \(i\)th of whom is permanently seated at position \((X_i, Y_i)\), distinct from all other coworkers.

Cole is currently at position \((X_A, Y_A)\), and would like to reach the unlimited free ice cream at a different position \((X_B, Y_B)\). Neither position is located at a coworker's seat.

Please help Cole determine the closest distance he'll need to get to another coworker in order to travel from \((X_A, Y_A)\) to \((X_B, Y_B)\) without leaving the building. Your answer will be accepted if it is within either \(10^{-6}\) or \(0.000001\%\) of the right answer.

# Constraints

\(1 \le T \le 800\)
\(1 \le N \le 800{,}000\)
\(2 \le X_R, Y_R \le 1{,}000{,}000{,}000\)
\(0 < X_i, X_A, X_B < X_R\)
\(0 < Y_i, Y_A, Y_B < Y_R\)

The sum of \(N\) across all buildings is at most \(3{,}000{,}000\).

# Input

Input begins with a single integer \(T\), the number of office buildings. For each building, there is first a line containing \(2\) space-separated integers, \(X_R\) and \(Y_R\). Then, there is a line containing \(4\) space-separated integers, \(X_A\), \(Y_A\), \(X_B\), and \(Y_B\). Then, there a line containing a single integer \(N\). Then, \(N\) lines follow, the \(i\)th of which consists of \(2\) space-separated integers, \(X_i\) and \(Y_i\).

# Output

For the \(i\)th building, print a line containing *"Case #i: "* followed by a single real number, the closest that Cole will need to get to another coworker in order to reach the free ice cream.

# Sample Explanation

In the first building, walking directly from \((3, 1)\) to \((17, 1)\) would take Cole within just 2 units of the coworker at \((10, 3)\). Instead, one optimal route might involve walking upward first, then across, and then back down, as illustrated below:

{{PHOTO_ID:441536274154579|WIDTH:450}}

The closest such a route gets to the coworker is \(7\) units (for example at coordinates \((10, 10)\).

In the second building, Cole's route must begin and end at a distance of \(\sqrt{4^2 + 2^2} \approx 4.47\) units from the coworker at \((10, 3)\). It's possible for Cole to get around them without getting any closer than that, for example with the following route:

{{PHOTO_ID:4816243665107323|WIDTH:450}}

In the third building, one optimal route for Cole might look as follows:

{{PHOTO_ID:440615224330860|WIDTH:280}}