Геометрия: задачи

A: Космический кегельбан

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

Каждая кегля представляет собой высокий цилиндр с основанием в виде круга радиусом \(r\) метров. Все кегли одинаковые. Кегли расставлены по следующим правилам. Кегли образуют \(n\) рядов, в первом ряду стоит одна кегля, во втором — две, и так далее. В последнем \(n\)-м ряду стоит \(n\) кеглей. Введем на плоскости систему координат таким образом, чтобы единица измерения была равна одному километру. Центр единственной кегли в первом ряду находится в точке \((0, 0)\). Центры кеглей во втором ряду находятся в точках \((–1, 1)\) и \((1, 1)\). Таким образом, центры кеглей в \(i\)-м ряду находятся в точках с координатами \((–(i – 1), i – 1)\), \((–(i – 3), i – 1)\), ..., \((i – 1, i – 1)\).

Игра происходит следующим образом. Используется шар с радиусом \(q\) метров. Игрок выбирает начальное положение центра шара \((x_c, y_c)\) и вектор направления движения шара \((v_x, v_y)\). После этого шар помещается в начальную точку и двигается не останавливаясь в направлении вектора \((v_x, v_y)\). Считается, что шар сбил кеглю, если в процессе движения шара имеет место ситуация, когда у шара и кегли есть общая точка. Сбитые кегли не меняют направления движения шара и не сбивают соседние кегли при падении.

На рисунке приведен пример расположения кеглей для \(r = 500\), \(n = 4\) и шара для \(q = 1000\), \(x_c = –2\), \(y_c = –2\), \(v_x = 1\), \(v_y = 1\).

Требуется написать программу, которая по заданным радиусу кегли \(r\), количеству рядов кеглей \(n\), радиусу шара \(q\), его начальному положению \((x_c, y_c)\) и вектору направления движения \((v_x, v_y)\) определяет количество кеглей, сбитых шаром.

Первая строка входных данных содержит два целых числа: \(r\) и \(n\), разделенных ровно одним пробелом (\(1 \le r \le 700\), \(1 \le n \le 200000\)).

Вторая строка входных данных содержит целое число \(q\) (\(1 \le q \le 10^9\)).

Третья строка входных данных содержит два целых числа \(x_c\) и \(y_c\), разделенных ровно одним пробелом (\(–10^6 \le x_c \le 10^6\), \(–10^6 \le y_c\), \(1000y_c \lt –(r + q)\)).

Четвертая строка входных данных содержит два целых числа \(v_x\) и \(v_y\), разделенных ровно одним пробелом (\(–10^6 \le v_x \le 10^6\), \(0 \lt v_y \le 10^6\)).

Программа должна вывести одно целое число — количество сбитых кеглей.

Ввод Вывод
500 4
1000
-2 -2
1 1
7

B: Кольцевая автодорога

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

В Генеральном плане также были обозначены требования к этой дороге. Она должна соответствовать статусу кольцевой — иметь форму окружности. Кроме этого, четыре крупные достопримечательности Флэтбурга должны быть в одинаковой транспортной доступности от дороги. Это предполагается обеспечить тем, что они будут находиться на равном расстоянии от неё. Расстоянием от точки расположения достопримечательности до дороги называется наименьшее из расстояний от этой точки до некоторой точки, принадлежащей окружности автодороги.

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

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

Программа получает на вход четыре строки. Каждая из них содержит по два целых числа: \(x_i\) и \(y_i\) — координаты места расположения достопримечательности. Никакие две достопримечательности не находятся в одной точке.

Все числа не превосходят 100 по абсолютной величине.

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

Во второй строке требуется вывести координаты центра дороги минимальной длины и её радиус. Если существует несколько разных способов построения дороги минимальной длины, необходимо вывести координаты центра и радиус любой из них. Координаты центра и радиус должны быть выведены с точностью не хуже \(10^5\) и не должны превышать \(10^9\) . Гарантируется, что существует хотя бы один план с такими параметрами.

ZA: Лапта

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

В первой строке входных данных содержатся два целых числа: \(D\) — максимальное расстояние удара и \(N\) — количество соперников на поле (\(1\le D \le 1000\), \(1 \le N \le 200\)). В следующих \(N\) строках задается по три целых числа — начальные координаты \(x_i\) и \(y_i\) и максимальная скорость \(v_i\) соответствующего игрока (\(-1000 \le x_i \le 1000\), \(0\le y_i\le 1000\), \(1\le v_i\le 1000\)), никакие два игрока не находятся изначально в одной точке. Игрок, бьющий мяч, находится в точка с координатами \((0, 0)\). Мяч выбивается в точку с неотрицательной ординатой (\(y\ge 0\)).

Выведите сначала время, которое потребуется игрокам, чтобы добежать до мяча, а затем координаты точки, в которую нужно выбить мяч. Если таких точек несколько, выведите координаты любой из них. Время и координаты нужно вывести с точностью не менее, чем \(10^{-3}\).

Ввод Вывод
10 2
1 1 1
-1 1 1
9.05539
0.00000 10.00000

ZB: Зал круглых столов

Единственный способ попасть в Зал Круглых Столов — пройти через Колонный Коридор. Стены Коридора изображаются на карте прямыми линиями, которые параллельны оси OY. Вход в Коридор находится снизу, а выход из Коридора в Зал — сверху. В Коридоре есть цилиндрические (на карте круглые) Колонны одинакового радиуса \(R\).

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

В первой строке входного файла заданы два числа \(X_L\) и \(X_R\) — \(x\)-координаты левой и правой стен Коридора. Во второй строке находится целое число \(R\) (\(1\le R\le 10^6\)) — радиус всех Колонн. В третьей — целое число \(N\) (\(1\le N\le 200\)), которое задает количество Колонн. Далее следуют \(N\) строк, в каждой из которых по два числа — \(x_i\) и \(y_i\) — координаты центра соответствующей Колонны.

Все входные координаты — целые числа, которые по модулю не превосходят \(10^6\).

Программа должна вывести одно число — искомый диаметр наибольшего Стола, выведенный с точностью не менее \(10^{-3}\). Если нельзя пронести ни одного Стола, то программа должна вывести 0.

Ввод Вывод
0 90
3
4
10 10
70 10
50 50
10 90
47