Задача A. Four-dimensional polytope ≡

Условие

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

Каждая вершина такого политопа задается четырьмя своими координатами (x, y, z, w). Каждое ребро представляет собой прямолинейный отрезок и задается парой соединяемых им вершин. Каждая грань представляет собой выпуклый многоугольник и задается набором своих ребер. Каждое тело представляет собой выпуклый многогранник и задается набором своих граней.

Сам политоп задается набором ограничивающих его трехмерных тел.

Требуется написать программу, вычисляющую объем сечения указанного политопа трехмерным подпространством при w = 0.

Формат входных данных

Во входных данных последовательно хранятся наборы сеточных элементов.

Вначале идет целое число V, за которым следует ровно 4 ⋅ V вещественных чисел, задающих координаты вершин.

Далее целое число E, за которым следует ровно 2 ⋅ E номеров вершин, попарно задающих ребра.

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

Вначале целое число ребер N, за которым следует N номеров этих ребер.

Аналогичным образом записываются тела, заданные номерами своих граней.

Нумерация сеточных элементов каждого вида начинается с нуля.

Формат выходных данных

Выходные данные должны содержать объем с точностью не менее 5 знаков после запятой.

Ограничения

Гарантируется, что все сеточные элементы являются невырожденными.

Координаты вершин лежат в диапазоне от  − 10 до 10.

Число элементов каждого вида не превосходит 1000.

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

5
-1.00000 -1.00000 -1.00000 -0.50000
 0.00000  1.00000 -1.00000 -0.50000
 1.00000  0.00000 -1.00000 -0.50000
 0.00000  0.00000  1.00000 -0.50000
 0.00000  0.00000  0.00000  0.50000

10
0 1
0 2
0 3
1 2
1 3
2 3
0 4
1 4
2 4
3 4

10
3 0 1 3
3 1 2 5
3 0 2 4
3 3 4 5
3 0 6 7
3 1 6 8
3 2 6 9
3 3 7 8
3 4 7 9
3 5 8 9

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

0.12500

Задача B. Звёзды под водой ≡

Условие

При разработке систем распознавания изображений часто большую проблему представляет получение размеченного набора данных (датасета). Сбор реальных изображений может быть затратным по времени и ресурсам. Технологии конструирования реалистичных виртуальных сцен могут помочь в такой ситуации.

В этой задаче требуется разработать программу, которая находит объекты на изображениях, сделанных под водой. Для тестирования мы подготовили несколько тысяч рендеров подводных сцен при помощи проекта на Unity, который можно скачать ЗДЕСЬ. Требуется определить, есть ли на этих картинках морские звезды и если есть, то находить их количество и положение.

Пример одной из таких картинок

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

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

Датасет доступен по этой ссылке. Он представляет из себя архив с картинками в формате png. Название картинки соответствует номеру теста. На каждой картинке может быть от нуля до трех морских звезд.

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

В первой строке выходного файла выведите количество тестов t, на которые вы собираетесь дать ответ. После этого выведите ответы на t тестов в следующем формате:

В первой строке каждого ответа выведите два одно целое число — номер теста на который вы собираетесь дать ответ. Во второй строке каждого ответа выведите количество звезд в этом тесте (если звезд на картинке не было, выведите ноль). Запрещается выводить больше чем три звезды для каждого ответа, иначе тест будет проигнорирован..

Для каждой звезды в отдельной строке выведите координаты (в пикселях) ограничивающего прямоугольника для этой звезды в формате x₁, y₁, x₂, y₂, где x₁, y₁ — координаты левого верхнего угла этого прямоугольника, а x₂, y₂ — координаты нижнего правого угла, разделенные одним пробелом. Выводить координаты ограничивающих прямоугольников звезд можно в любом порядке (соблюдая формат). Стоит считать, что начало координат находится в левом верхнем углу картинки. В файле не должно быть лишних пустых строк.

Будем считать, что звезда найдена верно, если:

• X₁, Y₁, X₂, Y₂ — координаты реального ограничивающего прямоугольника;
• x₁, y₁, x₂, y₂ — координаты найденного вами ограничивающего прямоугольника;
• Величина |x₁ − X₁| + |x₂ − X₂| составляет менее чем 10% от общей ширины картинки;
• Величина |y₁ − Y₁| + |y₂ − Y₂| составляет менее чем 10% от общей высоты картинки.

Для оценки будет использоваться величина, равная количеству правильно найденных звезд, поделенному на количество реально существующих звезд. Эта величина будет умножена на 100 и округлена вверх до целого числа.

Для проверки вашего решений отошлите файл с ответами в указанном выше формате.

В качестве среды разработки следует выбирать Answer text (расширение .txt).

Для генерации обучающей выборки рекомендуется воспользоваться нашим генератором.

Задача C. Позиционирование VR-шлема ≡

Условие

Начинающий программист Вася участвует в проекте по разработке собственного шлема виртуальной реальности.

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

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

Решение считается верным, если оно отличается от истинного положения шлема не более чем в 5-м знаке после запятой.

Формат входных данных

Входные данные содержат натуральное n, за которым следует набор из 4 × n вещественных чисел, определяющих координаты базовых станций (x_i, y_i, z_i) и расстояния до них d_i.

Формат выходных данных

Если задача имеет решение, выходные данные должны содержать целое число 1,
за которым следуют координаты шлема, указанные с точностью не менее 5 знаков после запятой.

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

Ограничения

Все расстояния корректны и указаны с точностью до 10-го знака после запятой.

 − 10 ≤ (x_i, y_i, z_i) ≤ 10, 0 ≤ d_i ≤ 50, 1 ≤ n ≤ 10⁵.

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

 4
-5.30710  7.24030 -1.23090  5.8376287360
-1.01140  2.40600  0.50000  1.6557115600
 0.35000  1.40000  3.56100  3.6476015421
 1.98000  1.75000 -2.05000  5.5483426363

1 -2.00000 3.28010 1.50000

 4
-1.09670  2.46050 -3.25040  4.3513370980
 0.53010 -1.37090 -3.25040  3.9144142014
 2.75010 -1.37090 -3.25040  4.3513370980
-2.44060  0.76030 -3.25040  4.7208526804

0

Задача D. Пушка и рождественское дерево ≡

Условие

Вася решил позаниматься НЕРЕАЛЬНЫМ занятием. Он решил пострелять из пушки по рождественскому дереву в новом году. Пушка уже направлена точно на цель по оси Х, но рассчитать точную траекторию полета ядра Вася сам не может. Вася просит помощи в этом сложном занятии, потому что уже поздняя ночь и он забыл все алгоритмы.

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

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

Файл с решением должен содержать реализацию класса UCannonSceneComponent.