silver_Target_Practice_II (USACO February_Contest)
Time limit: 2.5 seconds | Memory limit: 256 MB | Task type: batch
Algorithms: greedy, parametric search, binary search

Note: The time limit for this problem is 2.5s, 1.25 times the default.
Note: The large size of integers involved in this problem may require the use
of 64-bit integer data types (e.g., a "long long" in C/C++).
The Paris Moolympics are coming up and Farmer John is training his team of cows
in archery! He has set up the following exercise on the 2D coordinate plane.
There are $N (1 \leq N \leq 4 \cdot 10^4)$ axis-aligned rectangular targets and
$4N$ cows. Every cow must be assigned to a different target vertex. At moment
$i$, for
$1 \leq i \leq N$:
Target $i$ appears.
The $4$ cows assigned to its vertices shoot
at them.
If a cow's shot passes through the interior of the target
before it hits the assigned vertex or misses, the cows
fail
the
exercise.
The target disappears to make space for the next one.
Each cow is located on the $y$-axis $(x = 0)$, and each target is a rectangle
where target $i$ has its lower left coordinate at $(X_1, y_1^{(i)})$ and its
upper right coordinate at $(x_2^{(i)}, y_2^{(i)})$. The coordinates also satisfy
$1 \leq X_1 < x_2^{(i)}\leq 10^9$ and $1 \leq y_1^{(i)} <  y_2^{(i)} \leq 10^9$
(Note: $X_1$ is the same for every target).
In addition, each cow has a "focus" angle they are working on. Therefore, they
will turn at a specific angle when shooting. Given that their shot travels in a
straight line from their position towards their assigned vertex, the trajectory
of cow $i$'s arrow can be described by $s_i$ $(0 < |s_i| < 10^9)$, the slope of
the trajectory.
So that he can carefully examine the cows' technique, Farmer John wants to
minimize the distance between the furthest cows. If Farmer John were to
optimally assign each cow to a target vertex and place them on the $y$-axis, can
you help him determine what the minimum distance between the furthest cows would
be or if the cows will always fail the exercise?
Each input contains $T$ ($1 \leq T \leq 10$) independent test cases. The sum of
$N$ across all test cases is guaranteed to not exceed $4\cdot 10^4$.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains $T$ ($1 \leq T \leq 10$), the number of independent test
cases. Each test case is described as follows:
The first line of each test case contains two integers, $N$ and $X_1$, the
number of targets and the left-most $x$-coordinate of the targets respectively.
This is followed by $N$ lines with the $i$-th line consisting of three integers,
$y_1^{(i)}$, $y_2^{(i)}$, and $x_2^{(i)}$, the lower $y$-coordinate, the upper
$y$-coordinate, and the right $x$-coordinate of the $i$-th target respectively.
The last line consists of $4N$ integers, $s_1, s_2, \dots, s_{4N}$ where $s_i$
denotes the slope of cow $i$'s shot trajectory.
OUTPUT FORMAT (print output to the terminal / stdout):
The minimum possible distance between the furthest cows or $-1$ if the cows will
always fail the exercise.
SAMPLE INPUT:
3
2 1
1 3 6
4 6 3
1 -1 2 -2 3 -3 4 -4
2 1
1 3 6
4 6 3
1 1 2 2 3 3 4 4
2 1
1 3 3
4 6 3
1 -1 2 -2 3 -3 4 -4
SAMPLE OUTPUT:
17
-1
11
One optimal assignment for test case 1 is the following target vertices for cows
1-8 respectively:
$$(6, 1), (6,3), (3,4), (3,6), (1,4), (1,3), (1,6), (1,1)$$
This gives the following $y$ locations for cows 1-8 respectively:
$$-5, 9, -2, 12, 1, 6, 2, 5$$
This gives a minimum distance of $12-(-5) = 17$.
One reason the second test case is impossible is because it is impossible to
shoot the vertex at $(6, 3)$ (the top right vertex of target 1) without the shot
passing through the interior of target 1.
SCORING:
Input 2: $|S_i|$ is the same for all $1 \leq i \leq 4N$.
Input 3-9:
The sum of $N$ across all testcases is at most $1000$.
Inputs 10-15: No
additional constraints.
Problem credits: Suhas Nagar

Starter code:

Grader code:

Setup script:

Evaluation script: