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

Условие

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

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

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

Во входном файле "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

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

Условие

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

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

• изменение длин его ребер в константное (не нулевое) число раз;
• поворот на угол (кратный 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

Задача C. Точки на поверхности цилиндра ≡

Условие

Пусть имеется набор из n точек, расположенных на поверхности цилиндра. Каждая i-я точка задается своими цилиндрическими координатами: (z_i, φ_i), где z_i направлена вдоль вертикальной оси цилиндра, φ_i — полярный угол, указанный в радианах.

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

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

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

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

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

Ограничения

 − 10 < z_i < 10, 0 ≤ φ_i < 2 ⋅ π,

2 ≤ n ≤ 10⁵

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

 5
 0.13070 4.05001
 1.50600 1.94070
-1.98006 2.13080
-0.50601 2.94006
 1.87030 5.00000

1.27960

 5
-1.37060 0.20480
-1.25000 3.10100
 0.90640 2.00000
-1.00000 5.43070
-2.94080 3.75000

1.12036

Задача D. Муравьи на сетке ≡

Условие

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

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

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

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

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

Входной файл "input.txt" содержит число N, за которым следует набор
из 3 × N целочисленных индексов стартовых ячеек: X_i, Y_i, Z_i.

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

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

Ограничения

 − 10⁶ ≤ (X_i, Y_i, Z_i) ≤ 10⁶, 2 ≤ N ≤ 10⁵

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

5
1 19 37
-9 5 10
4 3 6
9 8 7
17 20 5

6

5
6 49 58
-9 -1 3
2 8 9
-1 2 0
2 8 9

0

Задача E. Траектория подвижной частицы ≡

Условие

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

Известно, что каждая такая частица должна двигаться вдоль ломаной линии, которая в моменты времени t_i проходит через установленные точки с координатами: (x_i, y_i), где i = 0, 1, …, (n − 1). При этом полагается, что на каждом интервале [t_i, t_i + 1] скорость частицы остается неизменной. В свою очередь, информация о положениях частицы в моменты времени t_i в дальнейшем может уточняться.

Помимо всего прочего ему также требуется эффективным образом обрабатывать запросы следующих видов:

mov i x y — обновить координаты положения частицы в момент времени t_i;

get a b — вернуть расстояние, пройденное частицей за время [a, b].

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

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

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

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

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

Ограничения

t_i < t_i + 1 ≤ 10, 2 ≤ n ≤ 10⁵, 0 < m ≤ 10⁴

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

5
0.00000 -3.87048  3.96100
2.53010 -2.97601  4.97030
4.09607 -2.24526  2.50780
7.12038  1.21090  4.84820
9.99999 -0.17846  4.20190

5
get      0.00000  9.99999
mov   1 -2.58070  4.98030
get      0.00000  4.09607
mov   2 -1.70250  2.67010
get      4.09607  9.99999

9.62361
4.13908
5.16991

5
0.53080 -0.25010 -1.96000
2.76090  3.04709 -0.34010
4.09601 -0.56010  0.05036
7.50430  3.36051  1.24607
8.75041  0.11308  3.70200

5
get      2.76090  4.09601
mov   3  3.75096  1.54670
get      3.81067  8.23060
mov   1  3.65040  0.87090
get      1.92304  2.01345

3.62826
7.80334
0.19539

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

Условие

Пусть имеется множество точек на плоскости, заданных своими двумерными координатами: M = {(x_i, y_i): i = 0, 1, …, n − 1}.

По двум заданным точкам A и B требуется найти такую точку C из M,
чтобы образованный ими треугольник {A, B, C} содержал в себе наибольшее число точек из M.
При этом точки, лежащие на границе такого треугольника, здесь также следует учитывать.

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

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

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

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

Ограничения

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

Точки A и B не совпадают между собой.

 − 10⁴ ≤ (x_i, y_i) ≤ 10⁴, 0 < n ≤ 10⁵

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

10
-7683 -1465
 1000  6970
-1096 -1613
 7052  3877
-8237  2965
 5089  6152
-7697  5970
 1340 -7370
 2068  1467
 4499 -3269

 1990 -5786
-6140 -5000

5

10
-4036  1190
 4691 -1023
 7809 -1023
 7021 -6507
 4691 -1023
-1000 -5000
 3096 -1023
 1570 -4210
 7809 -1023
 7809 -1023

-7500 -5103
-1059 -1023

9

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

Условие

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

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

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

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

Во входном файле "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

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

Условие

Рассмотрим конфигурацию из 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