Задача A. Горы в галактике Дзета ≡

Условие

Известно, что некоторая галактика Дзета состоит из планет, поверхность которых является идеальной сферой. На всех этих планетах расположены несколько гор, которые являются конусами. Будем говорить, что точка является основанием горы, если она является центром круга в основании соответствующего конуса. Основание любой горы находится на поверхности сферы. Вершины гор расположены по направлению вектора, проведённого из центра планеты к основанию горы.

Юный программист Вася путешествует по галактике на космическом корабле и встречает одну из таких планет радиусом R, которая расположена в начале координат. В корабле нет иллюминаторов, зато есть камера с углом обзора 90 градусов, которая может фотографировать, а также транслировать изображение с соотношением сторон 1:1. Вася решает сделать фотографию планеты в тот момент, когда камера находилась в положении (x_c, y_c, z_c) и была направлена в сторону вектора l⃗{x_l, y_l, z_l}. Поскольку по пути космический корабль могло развернуть, то дополнительно укажем, что вертикальная ось камеры была направлена в сторону вектора u⃗{x_u, y_u, z_u} (положительное направление вертикальной оси – проще говоря, «верх» камеры) (см. рис. 1). Известно, что на планете находятся N гор, каждая высотой h_i, и основания которых в момент фотосъёмки были расположены в точках пространства {x_i, y_i, z_i}.

Васе не терпится узнать, сколько и какие именно горы будет «видно» на его фотографии (рис. 2), и, пока изображение обрабатывается компьютером, он решил написать программу, чтобы выяснить это. Будем говорить, что гора «видна», если на фотографию попала её вершина. Помогите Васе написать программу, которая будет это определять.

Примечание

Гарантируется, что ни одна вершина горы в кадре не заслонена другой горой.

В качестве тестирующего модуля вы можете использовать этот визуализатор.

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

Каждая строка содержит соответственно:

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

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

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

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

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

Ограничения

50≤R≤500

 − 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≤20

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

100
200 0 0
-3 0 0
0 0 3
2
-100 0 0 10
100 0 0 10

1
2

350
508 362 -32.1
-1.631764 -1.077921 0.4188476
0.4669206 0.4323552 2.931732
4
-339.0739 -86.76899 -0.2563334 35.68471
71.48166 340.9988 -33.31894 58.20355
143.9016 280.8656 151.3501 46.14721
37.14282 -338.9936 -78.76414 65.93442

2
2
3