Задача A. Точки на n-мерном параллелепипеде ≡

Условие

Пусть имеется набор из m точек n-мерного евклидова пространства, заданных своими декартовыми координатами: (x1i, x2i, …, xni), где нижний индекс обозначает номер точки, а верхний — номер координаты.

Требуется определить, существует ли n-мерный параллелепипед (со сторонами, параллельными осям координат), на границе которого лежат указанные точки.

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

В начале входного файла "input.txt" хранятся два натуральных числа: m и n.

Далее следует m строк, содержащих координаты точек исходного множества: (x1i, x2i, …, xni).

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

Выходной файл "output.txt" должен содержать одно из следующих значений:

1 — если такой параллелепипед существует;

0 — в противном случае.

Ограничения

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

 − 10⁴ < xki < 10⁴, 0 < n ≤ 10, 0 < m ≤ 5 ⋅ 10⁴

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

 6 3
-3056 -5013 -4706
 6423  9875  1023
-3056 -5013  1023
 6423 -5013 -4706
-3056  9875 -4706
 6423 -5013  1023

1

 5 2
-3170 -1400
 4950 -1400
-3170  7030
  150  3500
 4950  7030

0

Задача B. Треугольник в параллелепипеде ≡

Условие

Пусть имеется параллелепипед со сторонами, параллельными осям координат: D = { (x, y, z): x_min ≤ x ≤ x_max, y_min ≤ y ≤ y_max, z_min ≤ z ≤ z_max} и некоторый треугольник T, заданный координатами своих вершин: (x₁, y₁, z₁), (x₂, y₂, z₂), (x₃, y₃, z₃).

Требуется определить площадь той части треугольника T, которая имеет общие точки с параллелепипедом D.

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

В начале входного файла "input.txt" записаны координаты двух наиболее удаленных вершин параллелепипеда: (x_min, y_min, z_min), (x_max, y_max, z_max).

Далее следуют координаты вершин треугольника: (x₁, y₁, z₁), (x₂, y₂, z₂), (x₃, y₃, z₃).

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

Выходной файл "output.txt" должен содержать площадь, указанную с точностью до 5-го знака после запятой.

Ограничения

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

x_min ≤ x_max, y_min ≤ y_max, z_min ≤ z_max.

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

-1.00000 -1.00000 -1.00000
 1.00000  1.00000  1.00000

-1.25000  0.56000  1.28090
-1.30000 -1.29010 -0.75000
 0.60790 -1.30700  1.30600

0.97386

-1.50000 -1.50000  1.00000
 0.50000  0.00000  1.50000

-3.70980  0.67000  3.20000
-4.60000 -1.86010  3.80250
 1.00000 -1.25000  4.10900

0.00000

Задача C. Пересечение двух пластин ≡

Условие

Пусть имеются две круглые плоские пластины, произвольным образом расположенные в трехмерном пространстве. Каждая такая пластина однозначно задается ортогональным к ней вектором (Nx_i, Ny_i, Nz_i), своим центром (Cx_i, Cy_i, Cz_i) и радиусом R_i.

Требуется определить наличие пересечения между указанными пластинами. Будем считать, что пластины пересекаются, если у них имеется как минимум одна общая точка.

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

В начале входного файла "input.txt" хранится набор вещественных значений, задающих первую пластину:
Nx₁, Ny₁, Nz₁, Cx₁, Cy₁, Cz₁, R₁.
Далее следует такой же набор, задающий вторую пластину:
Nx₂, Ny₂, Nz₂, Cx₂, Cy₂, Cz₂, R₂.

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

Выходной файл "output.txt" должен содержать:

1 — если заданные пластины пересекаются;

0 — в противном случае.

Ограничения

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

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

 0.59914  0.43486 -0.67224
 1.37001 -4.96720 -5.08104
 8.89915

 0.68033 -0.72560 -0.10314
 6.58011  2.42032  2.03280
 7.03841

1

 0.31968  0.82015 -0.47448
 0.37001 -8.76004 -5.38004
 8.01551

 0.24587 -0.88474  0.39594
 8.94060  7.42032 -0.33687
 9.03937

0

Задача D. Ловушка для подвижных частиц ≡

Условие

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

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

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

Определим кольцо, как область, заключенную между двумя окружностями с общим центром (x₀, y₀) и разными радиусами: r₂ > r₁ > 0. В этом случае исходное множество частиц можно условно разбить на три группы:

1. частицы, попадающие во внутренний круг с центром в точке (x₀, y₀) и радиусом r₁ > 0;
2. частицы, заключенные между двумя окружностями с радиусами r₁ и r₂;
3. частицы, лежащие за пределами внешнего круга с радиусом r₂ > r₁.

Рассмотрим поведение указанных частиц на временном интервале от 0 до T.

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

Требуется написать программу, которая по известному начальному положению частиц, исходным компонентам скорости и параметрам кольцевой области, производит расчет их траекторий в течение заданного промежутка времени. В качестве ответа вывести координаты положения частиц в равноотстоящие моменты времени t_k = k ⋅ (T / m), где k = 1, 2, …, m.

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

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

В первой строке входного файла "input.txt" содержатся параметры расчетной области: x₀, y₀, r₁, r₂. Во второй строке указано значение T, задающее длину временного интервала, и число его подынтервалов m. Далее следует натуральное число n и последовательность из 4 × n вещественных чисел, задающих начальные координаты и скорости каждой из частиц: x_i, y_i, u_i, v_i, где i = 1, 2, …, n.

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

Выходной файл "output.txt" должен содержать координаты положения частиц в моменты времени t_k (k = 1, 2, …, m), расположенные в том же порядке, что и во входном файле. Все значения должны быть указаны с точностью до 5-го знака после запятой.

Ограничения

Полагается, что ни одна из частиц в начальный момент времени не лежит на границе кольца.

2 ≤ r₁ ≤ (r₂ − 2) ≤ 10, 0 < T ≤ 20, 0 < m ≤ 10,

u_i² + v_i² ≤ 25, 0 < n ≤ 4000

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

 1.62400  4.86000  2.01152  4.21450
10.00000  4
 5
 2.24501 -2.75130 -0.46250  1.00000
-1.39080  6.92500  0.02731 -1.75240
-7.10643  2.32470  0.10561  0.27435
 2.07640  4.96800 -0.04658  0.94071
 3.00000  3.75400 -1.04060 -1.04520

 1.08876 -0.25130
-1.32252  2.54400
-6.84240  3.01057
 1.79231  6.39753
 0.09054  3.90417

-0.67633 -0.22719
 2.36153  1.88787
-6.57838  3.69645
 0.85566  4.23718
 1.22695  6.69642

-2.86015 -1.90584
 4.61717  4.01900
-6.31435  4.38232
 1.39629  4.06765
 3.58175  4.57937

-5.04397 -3.58449
 4.04359  7.86965
-6.05033  5.06820
 3.19249  5.59017
 0.69049  3.16606

Задача E. Распространение примеси ≡

Условие

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

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

Карта речной системы представляет собой ориентированный бесконтурный граф (сеть), в узлах которого располагаются очистные сооружения и разнообразные источники загрязнений. На входе указанной сети располагаются узлы, связанные с крупнейшими заводами. Каждый i-й завод непрерывно за одну единицу времени сбрасывает в реку ровно X_i тонн химических отходов.

Известно, что при прохождении через k-й промежуточный узел концентрация примеси изменяется на аддитивную константу F_k. Процент примеси, пропускаемый через ребро, направленное из узла с номером k в узел с номером l, определяется коэффициентом W_{k l}.

На выходе располагаются системы сбора воды с установленными на них датчиками, которые регистрируют количество примеси Y_j, проходящее через них за одну единицу времени.

По имеющимся данным требуется определить концентрацию примеси, выбрасываемую каждым отдельным заводом.

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

Во входном файле "input.txt" хранится карта речной сети, записанная в следующем виде.

Вначале идет пара натуральных значений n и m — число вершин и ребер в таком графе. За ними следует набор из m ребер, каждое из которых задается тремя значениями: k и l — номера вершин, которые оно соединяет; W_{k l} — весовой коэффициент.
При этом полагается, что нумерация вершин начинается с нуля.

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

Далее следует список, в котором каждому промежуточному узлу с номером k ставится в соответствие вещественная константа F_k, а каждому конечному узлу с номером j — значение Y_j.

Порядок следования узлов в таком списке не гарантирован!

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

Если задача имеет единственное решение, в выходной файл "output.txt" выводится строка 'SOLUTION:',
за которой следует список из номеров входных узлов i и соответствующих им значений X_i,
указанных с точностью до 5-го знака после запятой.

В противном случае, выходной файл должен содержать строку 'INFINITY!'.

Ограничения

Гарантируется, что точное решение всегда существует
и удовлетворяет следующим соотношениям: 0 ≤ X_i ≤ 10.

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

Гарантируется отсутствие висячих вершин
(не связанных ни с одним из ребер).

Число ребер, исходящих из одной вершины, не превосходит 10,
а их суммарный вес равен 1.

0 ≤ F_k ≤ 10, 2 ≤ n ≤ 1000, 0 < m.

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

10 9
0 3 1.00000
1 6 0.75000
1 4 0.25000
4 6 1.00000
6 3 0.50000
6 7 0.50000
2 5 1.00000
5 8 0.50000
5 9 0.50000

4 2.50480
5 1.39000
6 0.75630

3 5.30580
7 3.41550
8 1.91030
9 1.91030

SOLUTION:
0 1.89030
1 3.56990
2 2.43060

8 7
0 3 0.75000
0 4 0.25000
3 5 0.50000
3 6 0.50000
4 7 1.00000
1 4 1.00000
2 4 1.00000

3 1.36070
4 2.04590

5 2.71740
6 2.71740
7 7.41445

INFINITY!

Задача F. Коррекция фотоснимков ≡

Условие

Матрица фотоаппарата представляет собой прямоугольную таблицу размерности [n × m], состоящую из светочувствительных элементов (ячеек). В момент съемки каждой ячейке такой таблицы ставится в соответствие вещественное значение X_{i j}, указывающее ее состояние (интенсивность).

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

Коэффициент влияния каждой такой ячейки на полученное значение равен 1 / (2^l ⋅ N_l), где l — номер содержащего ее слоя, N_l — число ячеек в l-м слое.

Также для отдельно взятой модели фотоаппарата известно максимальное число слоев k, оказывающих влияние на результат измерения.

Для заданной матрицы Y, полученной в результате измерений, и радиуса воздействия k требуется восстановить исходные значения X_{i j}.

Значения фиктивных ячеек (лежащих за пределами матрицы) полагаются равными нулю.

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

В начале входного файла хранятся три натуральных числа: n, m и k.
Далее следует матрица результатов измерений Y, записанная в строчном формате.

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

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

Ограничения

0 ≤ Y_{i j} ≤ 10, 0 < n ⋅ m ≤ 40 000, 0 < k ≤ 6

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

9 6 3
0.26620 1.51042 0.59606 2.85301 0.76968 3.75000
1.51042 0.67130 3.09027 1.05324 4.38657 0.90856
0.59606 3.09027 1.13426 4.57754 1.29629 5.21412
2.88194 1.08217 4.61805 1.42940 5.60763 0.91435
0.87384 4.51388 1.43518 5.72916 1.08796 1.78819
4.13773 1.31944 5.72916 1.18055 2.03704 0.58449
0.98958 5.53819 1.12847 2.10648 0.76389 2.69097
4.98842 0.92592 1.98495 0.76389 2.95717 0.61343
0.49190 1.63773 0.54398 2.69097 0.61343 3.59375

0.00000 1.11111 0.00000 2.22222 0.00000 3.33333
1.11111 0.00000 2.22222 0.00000 3.33333 0.00000
0.00000 2.22222 0.00000 3.33333 0.00000 4.44444
2.22222 0.00000 3.33333 0.00000 4.44444 0.00000
0.00000 3.33333 0.00000 4.44444 0.00000 1.11111
3.33333 0.00000 4.44444 0.00000 1.11111 0.00000
0.00000 4.44444 0.00000 1.11111 0.00000 2.22222
4.44444 0.00000 1.11111 0.00000 2.22222 0.00000
0.00000 1.11111 0.00000 2.22222 0.00000 3.33333

Задача G. Минимальная длина ограды ≡

Условие

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

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

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

Во входном файле "input.txt" записано натуральное число n, за которым следует ровно n пар вещественных чисел (x_i, y_i), отвечающих за координаты исходных точек.

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

Выходной файл "output.txt" должен содержать ответ, записанный с точностью до 5-го знака после запятой.

Ограничения

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

 − 10 ≤ (x_i, y_i) ≤ 10, 3 ≤ n ≤ 10⁵

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

10
-1.51000 -4.12000
-3.10200 -2.30000
-4.10950 -0.25000
-4.00000  2.09010
-3.26000  3.25000
-1.40801  3.24050
 0.24070  1.34050
 1.28000 -0.50000
 1.75060 -2.57000
 1.00000 -4.36000

21.48729

10
-3.10200 -2.30000
 1.00400 -0.50000
-4.10950  1.25000
 0.00000 -0.59010
 1.00000 -1.20400
-1.36000  3.48020
 0.24070  1.34050
-1.51000 -4.12000
 2.56000  3.10600
 2.10340 -2.57000

23.21245

Задача H. Подобные многоугольники ≡

Условие

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

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

• изменение длин его ребер в константное (не нулевое) число раз;
• поворот на угол (кратный 90^∘) относительно некоторой фиксированной точки;
• параллельный перенос;
• смена направления обхода (с левостороннего на правостороннее и наоборот).

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

Во входном файле "input.txt" указано натуральное n, за которым следует набор из 2 ⋅ n вершин
(сначала для первого, а затем — для второго многоугольника),
записанных в виде пар целых десятичных чисел: (x_i, y_i).

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

Выходной файл "output.txt" должен содержать одно из следующих значений:

1 — если оба многоугольника подобны между собой;

0 — в противном случае.

Ограничения

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

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

 − 10⁴ ≤ (x_i, y_i) ≤ 10⁴, 3 ≤ n ≤ 10⁵

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

5
-300 300
-100 500
 200 400
 200 200
-100 100

 250 120
 150 220
  50 120
 100 -30
 200 -30

1

5
 100 200
   0 400
 300 300
 300 100
   0   0

 350 150
 150 320
  50 220
 100   0
 200   0

0

Задача I. Треугольные конфигурации ≡

Условие

Рассмотрим конфигурацию из n прямых на плоскости. Требуется определить число всех треугольных ячеек, образованных в результате разбиения плоскости указанным набором прямых.

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

Во входном файле "input.txt" записано натуральное число n, за которым следует ровно n прямых. Каждая прямая задается парой несовпадающих точек: (Ax_i, Ay_i), (Bx_i, By_i).

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

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

Ограничения

Гарантируется, что никакие две прямые не совпадают между собой.

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

 − 10⁴ ≤ (Ax_i, Ay_i, Bx_i, By_i) ≤ 10⁴, 3 ≤ n ≤ 300

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

5
  0 -20  15 -20
-10  10  35 -35
  0   0   0 -10
-10   0  30   0
-20   0   0  20

3

5
-10   0   0 -20
-20 -10 -10 -30
  0   0  10  24
  0  10  10 -10
-10   0   0  24

0

Задача J. Точки на планарном разбиении ≡

Условие

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

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

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

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

Во входном файле "input.txt" записано натуральное число n, за которым следует ровно n пар целых десятичных чисел (x_i, y_i), задающих координаты вершин планарного подразбиения.

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

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

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

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

Для точек, лежащих за пределами каких либо ячеек, в качестве ответа необходимо вывести  − 1.

Ограничения

Гарантируется, что ни одна из искомых точек не попадает на границу ячейки.

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

 − 10⁴ ≤ (x_i, y_i) ≤ 10⁴, 3 ≤ n ≤ 10³, 0 < k ≤ 3 ⋅ 10⁵

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

5
200 100
100 200
200 200
300 300
150 350

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

4
190 175
100 100
190 203
270 300

0
-1
2
1