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

Условие

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

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 20 000, 0 ≤ d ≤ 1000, 0 ≤ a_i ≤ 10⁹

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

3 4
10 15 14

1

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

Условие

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

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

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

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

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

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

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

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

Ограничения

3 ≤ X, Y ≤ 2000, r ≥ 1

1 ≤ x₀ − r < x₀ + r ≤ X, 1 ≤ y₀ − r < y₀ + r ≤ Y

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

3 3
.#.
###
.#.

1 2 2 1

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

Условие

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

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

Первая строка входных данных содержит 3 целых числа x_c, y_c, r_c — координаты и радиус мины. Вторая строка содержит одно целое число N — количество вершин в многоугольнике, описывающем корабль. Следующие N строк содержат N пар чисел (x_i, y_i) (по одной паре в строке) — координаты вершин выпуклого многоугольника, описывающего корабль, в порядке обхода по часовой стрелке.

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

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

Ограничения

 − 1000 ≤ x_c, y_c, r_c, x_i, y_i ≤ 1000

3 ≤ N ≤ 10³

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

Решения, работающие для  − 10 ≤ x_c, y_c, r_c, x_i, y_i ≤ 10, оцениваются из 50 баллов. Баллы выставляются за каждый успешно пройденный тест.

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

1 1 1
4
0 0
0 1
1 1
1 0

0.785398163

0 0 1
3
0 0
0 1
1 0

0.5

0 0 4
4
0 0
0 2
4 4
2 0

7.07035