Задача A. Перепад глубины

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:100  

Условие

Автономный необитаемый подводный аппарат проплыл по заданной траектории, записав последовательность целых чисел ai — глубину своего погружения в метрах на i-й секунде.

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

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

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

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

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

Выходные данные должны содержать единственное целое число — наименьшее количество удаляемых элементов.

Ограничения

1 ≤ n ≤ 20 000, 0 ≤ d ≤ 1000, 0 ≤ ai ≤ 109

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

Стандартный вход Стандартный выход
1
3 4
10 15 14
1

Задача B. Отладка шарика

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:100  

Условие

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

Для отладки Вася сделал скриншоты своего приложения (шар на них должен превратиться в круг). Скриншот представлен прямоугольным массивом символов, в котором символ "#" представляет красный пиксель, а символ "." — чёрный пиксель.

Если шар нарисован правильно, то красными будут только те пиксели, координаты которых (x; y) удовлетворяют условию (x − x0)2 + (y − y0)2 ≤ r2, где x0, y0, r — неизвестные целые числа.

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

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

Первая строка входных данных содержит целые числа X Y — ширину и высоту прямоугольника. Следующие Y строк содержат по X символов "#" и "." каждая — описание изображения.

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

Выходные данные должны содержать целые числа 1 x0 y0 r, если изображение является правильным, и число 0 в противном случае. Координаты отсчитываются от верхнего левого угла.

Ограничения

3 ≤ X, Y ≤ 2000, r ≥ 1

1 ≤ x0 − r < x0 + r ≤ X, 1 ≤ y0 − r < y0 + r ≤ Y

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

Стандартный вход Стандартный выход
1
3 3
.#.
###
.#.
1 2 2 1

Задача C. Морской бой

Автор:И. Блинов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

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

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

Первая строка входных данных содержит 3 целых числа xc, yc, rc — координаты и радиус мины. Вторая строка содержит одно целое число N — количество вершин в многоугольнике, описывающем корабль. Следующие N строк содержат N пар чисел (xi, yi) (по одной паре в строке) — координаты вершин выпуклого многоугольника, описывающего корабль, в порядке обхода по часовой стрелке.

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

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

Ограничения

 − 1000 ≤ xc, yc, rc, xi, yi ≤ 1000

3 ≤ N ≤ 103

Описание подзадач и системы оценивания

Решения, работающие для  − 10 ≤ xc, yc, rc, xi, yi ≤ 10, оцениваются из 50 баллов. Баллы выставляются за каждый успешно пройденный тест.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 1 1
4
0 0
0 1
1 1
1 0
0.785398163
2
0 0 1
3
0 0
0 1
1 0
0.5
3
0 0 4
4
0 0
0 2
4 4
2 0
7.07035

0.272s 0.013s 17