Задача B. Горы в галактике Дзета 2: Удачный кадр ≡

Условие

Перед прочтением условия задачи рекомендуется ознакомиться с задачей «Горы в галактике Дзета».

Юный программист Вася продолжает своё путешествие по галактике Дзета на космическом корабле. Корабль оборудован камерой с углом обзора 90 градусов, которая может фотографировать, а также транслировать изображение с соотношением сторон 1:1. Вася обнаружил в начале координат планету радиуса R, которая вращается с угловой скоростью ω вокруг оси z (ось, направляющий вектор которой равен {0, 0, 1} (см. рис. 1).

Если ω  > 0, то планета вращается против часовой стрелки, и наоборот. На планете находится N гор. Гора номер i имеет высоту h_i и в момент времени t = 0 координаты основания {x_i, y_i, z_i}. Вася останавливает свой корабль и направляет камеру, которая находится в координатах (x_c, y_c, z_c), в сторону вектора l⃗{x_l, y_l, z_l}. Вертикальная ось камеры направлена в сторону вектора u⃗{x_u, y_u, z_u} (положительное направление вертикальной оси – проще говоря, «верх» камеры) (см. рис. 2).

Вася хочет дождаться такого момента времени t, при котором в область видимости камеры попадёт максимально возможное количество вершин гор с этого ракурса. Поскольку нашего путешественника ждут другие планеты, ему требуется сделать фотографию до того, как планета совершит полный оборот с момента t = 0. Требуется написать программу, которая определит такое время t и выдаст список гор, видимых на фотографии в этот момент времени. Гора «видна», если на фотографию попала её вершина.

Для отладки решения вы можете использовать этот визуализатор.

Формат входного файла

Первые 4 строки содержат:

1. Вещественное число R, вещественное число ω;
2. Вещественные числа x_c, y_c, z_c – координаты камеры в момент времени t;
3. Вещественные числа x_l, y_l, z_l – координаты направляющего вектора камеры;
4. Вещественные числа x_u, y_u, z_u – координаты направляющего вектора «верха» камеры;
5. Натуральное число N;

В следующих N строках содержатся вещественные числа x_i, y_i, z_i, h_i – координаты оснований гор и их высоты.

Формат выходного файла

В первой строке требуется вывести одно число t – оптимальный момент времени для съёмки.

Во второй строке требуется вывести одно число k – количество гор, которые будут видны в кадре в момент времени t.

В следующих k строках требуется вывести упорядоченные по возрастанию номера видимых в кадре гор. Горы нумеруются в порядке расположения во входных данных, начиная с 1.

Если не существует момент t, при котором видна хотя бы одна вершина горы, выведите  − 1. Если существует несколько оптимальных решений t, выведите любое из них.

Ограничения

50≤R≤500

 − 30≤ω ≤30

 − 5000≤x_c, y_c, z_c, x_l, y_l, z_l, x_u, y_u, z_u, x_i, y_i, z_i≤5000

R / 10≤h_i≤R / 5

1≤N≤20000

Изображения вершин на камере никогда не совпадают.

Примеры тестов

500 17.75277
1000 0 0
-5 0 0
0 0 6
2
500 0 0 50
-500 0 0 50

10
1
2

423.6367 20.04418
563 -449 80
-3.318433 2.189247 -0.4418194
-0.460992 0.3041271 4.969406
5
-94.92951 347.2672 223.298 79.4897
105.1314 337.9636 -232.8005 79.1225
118.6561 358.101 192.7497 54.06856
-342.1483 -249.4405 13.49226 80.01097
-17.6792 124.43 -404.5648 58.64312

9.45
5
1
2
3
4
5