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

Автор:Dmitriy Merzlyakov   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:1512 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

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

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

Если ω  > 0, то планета вращается против часовой стрелки, и наоборот. На планете находится N гор. Гора номер i имеет высоту hi и в момент времени t = 0 координаты основания {xi, yi, zi}. Вася останавливает свой корабль и направляет камеру, которая находится в координатах (xc, yc, zc), в сторону вектора l⃗{xl, yl, zl}. Вертикальная ось камеры направлена в сторону вектора u⃗{xu, yu, zu} (положительное направление вертикальной оси – проще говоря, «верх» камеры) (см. рис. 2).

Рис. 1
Рис. 2

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

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

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

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

  1. Вещественное число R, вещественное число ω;
  2. Вещественные числа xc, yc, zc – координаты камеры в момент времени t;
  3. Вещественные числа xl, yl, zl – координаты направляющего вектора камеры;
  4. Вещественные числа xu, yu, zu – координаты направляющего вектора «верха» камеры;
  5. Натуральное число N;

В следующих N строках содержатся вещественные числа xi, yi, zi, hi – координаты оснований гор и их высоты.

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

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

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

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

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

Ограничения

50R500

 − 30≤ω ≤30

 − 5000xc, yc, zc, xl, yl, zl, xu, yu, zu, xi, yi, zi5000

R / 10hiR / 5

1N20000

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
500 17.75277
1000 0 0
-5 0 0
0 0 6
2
500 0 0 50
-500 0 0 50
10
1
2
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

0.254s 0.011s 17