Задача A. Вписанный цилиндр ≡

Условие

Пусть имеется некоторый выпуклый многогранник P и проходящая через него прямая L, заданная в параметрическом виде:

X(t) = X₀ + t ⋅ UD, Y(t) = Y₀ + t ⋅ VD, Z(t) = Z₀ + t ⋅ WD, где D = √U² + V² + W², t — произвольный скалярный параметр.

Требуется для некоторого заданного значения R определить цилиндр максимально возможной высоты
с осью L и радиусом R, целиком лежащий внутри многогранника P.

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

В начале входного файла "input.txt" записано число N, за которым следует 3 × N вещественных координат вершин.

Далее указано число M, за которым следует M граней, записанных в следующем виде.

Вначале для каждой грани указано число ее вершин, за которым следуют их индексы,
перечисленные в порядке их обхода для получения ограничивающего цикла грани.
При этом полагается, что нумерация вершин начинается с нуля.

В окончании входного файла указан набор вещественных значений:
X₀, Y₀, Z₀, U, V, W, R.

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

Если задача имеет решение, в выходной файл "output.txt" выводится число 1,
за которым следуют границы параметрического интервала,
задающего положение цилиндра на оси L,
указанные с точностью до 5-го знака после запятой
и расположенные в порядке возрастания.

В противном случае выходной файл должен содержать число 0.

Ограничения

Координаты всех вершин по модулю не превосходят 10.
Число вершин и граней не превосходит 100.

Прямая обязательно проходит сквозь внутреннюю
часть многогранника.

 − 10 ≤ (X₀, Y₀, Z₀, U, V, W) ≤ 10, 0 < R ≤ 10.

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

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

8
-1.00000 -1.00000 -1.00000
-1.00000 -1.00000  1.00000
-1.00000  1.00000  1.00000
-1.00000  1.00000 -1.00000
 1.00000 -1.00000 -1.00000
 1.00000 -1.00000  1.00000
 1.00000  1.00000  1.00000
 1.00000  1.00000 -1.00000

6
4 0 1 2 3
4 4 5 6 7
4 0 1 5 4
4 1 2 6 5
4 2 3 7 6
4 3 0 4 7

-0.50000 -0.50000 -0.50000
 1.00000  1.00000  1.00000
 0.50000

1
-0.15892  1.89097

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

Задача C. VR-обсерватория ≡

Условие

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

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

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

В начале входного файла "input.txt" записано натуральное число N, за которым следует ровно 3 ⋅ N координат точек (X_i, Y_i, Z_i).

Далее записано число M, за которым следует M запросов, каждый из которых задается вектором направления →D_j = (U_j, V_j, W_j) и радиусом R_j.
При этом полагается, что длина вектора →D_j соответствует фокусному расстоянию.

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

Выходной файл "output.txt" должен содержать M целых чисел — ответы на каждый запрос.

Ограничения

Гарантируется, что суммарное число точек во всех запросах не превосходит 10⁶.

Все входные значения являются целыми десятичными числами.

 − 10⁶ ≤ (X_i, Y_i, Z_i) ≤ 10⁶,  − 10⁶ ≤ (U_j, V_j, W_j) ≤ 10⁶, 0 < |→D_j|, 0 ≤ R_j ≤ 10⁶

1 ≤ N ≤ 10⁵, 1 ≤ M ≤ 10⁵

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

10
 40  25 -31
 12 -36  24
-45  10  37
-13  26 -51
 30  32  64
-16 -17  20
 21  23  35
 46 -14  18
 10 -30  20
 39 -19 -45

5
 3 -3 -2  0
 1 -3  2  0
 1  1  1  9
 7 -5  8  1
 1 -1 -1  8

0
2
4
0
5

Задача D. Кубик Рубика ≡

Условие

Вам необходимо создать UV-развёртку для куба.

Центр куба должен находиться в центре координат, длина ребра куба составляет 2 метрa.

Цвета ячеек кубика Рубика:

Сверху белый, снизу желтый.

С положительного направления оси OX зелёный, с отрицательного направления оси OX синий.

С положительного направления оси OY красный, с отрицательного направления оси OY оранжевый.

Текстура каждой грани кубика представляет из себя квадрат 450 на 450 пикселей, с девятью внутренними квадратами, размером 130 на 130 пикселей, разделенными чёрными полосами, шириной 15 пикселей.

Текстура доступна по ссылке.

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

Источник света:

Камера:

Render Engine: Eevee

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

Во входном файле содержатся x, y, z — координаты камеры в метрах и rx, ry, rz — углы поворота в радианах.

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

В качестве решения следует отправлять файл формата OBJ (расширение .obj). Размер файла не должен превышать 999997 Байт.

Материал следует назвать "solve". При создании .obj файла, его необходимо назвать "solve", так, чтобы у вас получились файлы "solve.obj" и "solve.mtl".

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

-2.49768 4.37707 3.69415
52.7631 0 209.466

Смотри рис. 4

0.232152 1.52857 -1.42144
119.549 0.665502 130.752

Смотри рис. 5