Задача A. Забор в парке
Условие
В бесконечном квадратном парке деревья образуют квадратную решётку с шагом 1 метр.
Часть парка было решено оградить забором, который представляет собой многоугольник с
заданными координатами вершин. Деревья, которые в точности попадают на
вершины или стороны многоугольника, придётся срубить. Необходимо выяснить количество таких деревьев.
Программа должна, получив на входе число вершин многоугольника N и их
целочисленные координаты (x1, y1), …,
(xN, yN), определить количество точек с целочисленными
координатами, лежащих на границе этого многоугольника.
Стороны многоугольника не самопересекаются.
Формат входного файла
Входной файл содержит число
N, за которым следует
N пар координат
x1 y1 …
xN yN
Формат выходного файла
Выходной файл должен содержать единственное число — количество точек.
Ограничения
3 ≤
N ≤ 1000,
0 ≤
xi,
yi ≤ 10
7,
исходные данные таковы, что результат не превосходит 2
31−1.
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
3
0 0 2 0 0 2
|
6
|
Задача B. Ближайшее число - 1
Условие
Дан массив A, состоящий из N неотрицательных целых чисел.
Назовём правым (левым) соседом нулевого элемента ближайший к
нему справа (слева) ненулевой элемент.
Требуется построить массив B, который получается из массива A заменой
каждого нулевого элемента на его ближайшего соседа в массиве A.
Если оба соседа отсутствуют либо расстояния до них равны,
замена не производится (элемент остаётся нулевым).
Формат входного файла
Входной файл содержит число
N, за которым следует
N целых чисел — элементы массива
A.
Формат выходного файла
Выходной файл должен содержать
N целых чисел — элементы массива
B.
Ограничения
1 ≤
N ≤ 10000, 0 ≤
Ai ≤ 10000
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
5
0 0 1 0 2
|
1 1 1 0 2
|
| 2 |
4
8 0 0 6
|
8 8 6 6
|
Задача C. Муравей и дерево
Условие
Муравей находится в лесу с плоской поверхностью почвы в точке с координатами
(x1, y1), и направляется в точку
(x2, y2).
В лесу растёт дерево, основание ствола которого имеет форму круга с центром в точке
(xT, yT) и радиусом RT.
Дерево, возможно, помешает муравью дойти до цели по прямой. В таком случае
ему придётся обойти дерево вокруг ствола.
Требуется определить длину кратчайшего пути для муравья.
Формат входного файла
Входной файл содержит вещественные числа
x1 y1
x2 y2
xT yT RT.
Формат выходного файла
Выходной файл должен содержать единственное вещественное число — длину кратчайшего пути.
Абсолютная ошибка результата не должна превосходить 0.01
(т.е. следует выводить число с точностью не менее 3 знаков после запятой).
Ограничения
Все числа во входном файле находятся в диапазоне от 0 до 1000.
(x1 − xT)2 +
(y1 − yT)2 ≥
RT2,
(x2 − xT)2 +
(y2 − yT)2 ≥
RT2
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
0 0 4 4 2 2 1
|
6.014
|
Задача D. Интернет по ЛЭП
Условие
Один из интернет-провайдеров решил опробовать новую технологию — передачу данных по линиям электропередач.
Для этого на подстанциях были установлены N ретрансляторов.
Рассмотрим i-й ретранслятор и провод от него к другому ретранслятору.
Количество ретрансляторов, сигнал от которых к i-му проходит через рассматриваемый провод,
назовем нагрузкой на данный провод для i-го ретранслятора.
Максимум из нагрузок на все провода для i-го ретранслятора
называется нагрузкой на данный ретранслятор.
Известно, что по проводам электросети сигнал может пройти
от одного ретранслятора к другому единственным образом.
Требуется написать программу, которая по заданной схеме электросети
подсчитает нагрузку на каждый ретранслятор.
Формат входного файла
Во входном файле содержится число
N — количество ретрансляторов, за которыми
следуют
N − 1 пар чисел
ui vi, означающих,
что
i-ый провод соединяет ретрансляторы
ui и
vi.
Формат выходного файла
В выходном файле должно содержаться
N чисел
a1 a2… aN,
где
ai — нагрузка на
i-ый ретранслятор.
Ограничения
1 ≤ N ≤ 100000.
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
3
1 2
2 3
|
2 1 2
|
| 2 |
4
1 2
1 3
1 4
|
1 3 3 3
|
