Задача 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

Задача B. Спектральная классификация звёзд ≡

Условие

Вам необходимо разработать фрагментный шейдер для визуализации звёзд в зависимости от температуры звезды T.

Спектральная классификация звёзд

• T ≤ 5000 — красные звёзды
• 5000 < T ≤ 8000 — жёлтые звёзды
• 8000 < T ≤ 10000 — белые звёзды
• 10000 < T — голубые звёзды

Шейдер проверяется на основе попиксельного сравнения рендеров. В качестве метрики для сравнения рендеров используется величина dssim по каждому цветовому каналу. Баллы за каждый тест начисляются в зависимости от величины метрики.

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

Во входном файле содержатся T — температура звезды.

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

Для прохождения тестов необходимо объявить переменную, в которую подставляются значения температур проверяющим модулем следующим образом:
uniform float T

В качестве решения следует отправлять файл формата FS (расширение .fs) на GLSL. В качестве среды разработки необходимо указывать Python.

Для тестирования работы фрагментного шейдера можете использовать онлайн средства, например, Shdr Editor

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

6000

Смотри рис. 1

11000

Смотри рис. 2

Задача C. Старые лампы ≡

Условие

Имеются 3 подключенных к одному контроллеру лампы. Левая (далее Л), средняя (далее С) и правая (далее П)

Каждая из ламп имеет некоторую, неизвестную заранее, яркость. Каждый такт загорается одна лампа, номер которой определяется неизменяющейся последовательностью. Алгоритм определения номера загорающейся лампы смотреть в файле SceneControlScript.cs. После чего у загоревшейся лампы снимается 1 единица яркости.

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

Для реализации алгоритма вам предоставляется сцена Unity, на которой расположены 3 источника света. Взаимодействие с ними реализовано в дополнительном объекте controller. Код с вашим алгоритмом должен находиться в предусмотренном классе Solution. Другие изменения в сцене учтены не будут.

• Объект controller предоставляет следующие функции для работы со сценой:
• controller.Pause() - останавливает моделирование ("лампочки" перестают зажигаться).
• controller.Resume() - запускает моделирование с того же момента на котором оно было остановлено.
ВАЖНО!: Pause и Resume взаимодействуют с внутреннем временем сцены, это означает что функции FixedUpdate приостанавливают и продолжают свою работу.
• controller.getCurentTime() - возвращает количество тактов с начала моделирования.
• controller.getIntensityOf(int index) - возвращает оставшуюся яркость лампы по индексу (Л - 0, С - 1, П - 2).
• controller.getLamps() - возвращает массив объектов ламп.
• controller.getLamps().Enabled - свойство возвращающее true/false в зависимости от того горит ли лампа.
• controller.setAnswer(int answer) - заканчивает моделирование, записывает в выходной файл переданное в данную функцию значение. (Предполагается что вывод количества тактов будет передан в данную функцию).

Изначально сцена находится на паузе. Моделирование начнется как только вы вызовете controller.Resume(). Кроме того, лимит горения ламп может быть большим.

Проект https://github.com/zokter/OldLamps.git, Вам осталось реализовать класс Solution.

Вы можете тестировать свои решения, изменяя данные, содержащиеся в файле input.txt в коренном репозитории проекта.

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

Входной файл input.txt содержит строку состоящую из 3-х чисел, разделенных пробелами, x, y, z - определяющими начальную яркость для каждой из ламп Л, С, П соответственно.

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

Файл с решением должен содержать реализацию класса Solution. Количество секунд, полученное вашим решением, должно быть представлено целым числом. Ответ необходимо выводить при помощи controller.setAnswer(int answer).

Ограничения

0 ≤ x ≤ 10⁶

0 ≤ y ≤ 10⁶

0 ≤ z ≤ 10⁶

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

1 1 1

3