Замечание: время на тест 2.5 сек, по умолчанию 1.25.
Замечание: необходимо использовать 64-битные типы данных
(например "long long" в C/C++).
Фермер Джон тренирует своих коров стрельбе из лука следующим
упражнением на координатной плоскости.
Всего имеется \(N (1 \leq N \leq 4 \cdot 10^4)\) прямоугольных мишеней
со сторонами
параллельными осям координат и \(4N\) коров. Каждая корова должна быть назначена
различной вершине прямоугольника. В момент \(i\), для \(1 \leq i \leq N\):
- Цель \(i\) появляется.
- \(4\) коров, назначенные своим вершинам, стреляют по ним.
- Если выстрел коровы попадает во внутренность мишени, прежде чем он попадёт
в назначенную вершину или пройдёт мимо, корова не выполнила
упражнение.
- Мишень исчезает, чтобы освободить место для следующей мишени.
Каждая корова расположена на \(y\)-оси \((x = 0)\), и каждая мишень - это
прямоугольник, где мишень \(i\) имеет нижний левый угол в точке
\((X_1, y_1^{(i)})\) и правый верхний угол в точке \((x_2^{(i)}, y_2^{(i)})\).
Эти координаты также удовлетворяют условиям
\(1 \leq X_1 < x_2^{(i)}\leq 10^9\) и
\(1 \leq y_1^{(i)} < y_2^{(i)} \leq 10^9\)
(Замечание: \(X_1\) одно и то же для каждой мишени).
В дополнение, каждая корова имеет свой "фокусный угол", где она может работать.
Поэтому корова поворачивается на этот специфический угол, когда стреляет.
Полагая, что их стрела летит по прямой от их позиции к назначенной вершине
траектория стрелы \(i\)'-ой коровы может быть описана \(s_i\)
\((0 < |s_i| < 10^9)\), наклоном траектории.
ФД хочет минимизировать расстояние между самыми дальними коровами.
Если ФД оптимально назначит каждой корове её целевую вершину и оптимально
разместит их на оси \(y\), вычислите минимальное расстояние между самыми
дальними коровами или коровы всегда не выполнят упражнение.
Каждый тест содержит \(T\) (\(1 \leq T \leq 10\)) независимых подтестов.
Гарантируется, что сумма всех \(N\) по всем подтестам не превысит \(4\cdot 10^4\).
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(T\) (
\(1 \leq T \leq 10\)), количество независимых
подтестов. Каждый подтест задаётся следующим образом:
Первая строка подтеста содержит два целых числа \(N\) и \(X_1\),
количество мишеней и самую левую координату мишеней соответственно.
Затем следуют \(N\) строк, где \(i\)-ая строка содержит 3 целых числа
\(y_1^{(i)}\), \(y_2^{(i)}\), \(x_2^{(i)}\), - нижняя \(y\)-координата,
верхняя \(y\)-координата и правая \(x\)-координата \(i\)-ой мишени соответственно.
Последняя строка состоит из \(4N\) целых чисел \(s_1, s_2, \dots, s_{4N}\)
где \(s_i\) обозначает наклон траектории выстрела \(i\)-ой коровы.
ФОРМАТ ВЫВОДА (на экран / stdout):
Минимальное возможное расстояние между самыми дальними коровами или
\(-1\) если коровы всегда не справятся с упражнением.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|
17
-1
11
|