На планете Плюк открылся новый космический кегельбан. Поле для кегельбана представляет собой бесконечную плоскость, на которой расставлены кегли.
Каждая кегля представляет собой высокий цилиндр с основанием в виде круга радиусом \(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 |
7 |
К 2110 году город Флэтбург, являясь одним из крупнейших городов мира, не имеет обходной автомагистрали, что является существенным препятствием для его развития как крупнейшего транспортного центра мирового значения. В связи с этим ещё в 2065 году при разработке Генерального плана развития Флэтбурга была определена необходимость строительства кольцевой автомобильной дороги.
В Генеральном плане также были обозначены требования к этой дороге. Она должна соответствовать статусу кольцевой — иметь форму окружности. Кроме этого, четыре крупные достопримечательности Флэтбурга должны быть в одинаковой транспортной доступности от дороги. Это предполагается обеспечить тем, что они будут находиться на равном расстоянии от неё. Расстоянием от точки расположения достопримечательности до дороги называется наименьшее из расстояний от этой точки до некоторой точки, принадлежащей окружности автодороги.
Дирекция по строительству города Флэтбурга, ответственная за постройку кольцевой автодороги, решила привлечь передовых программистов для выбора оптимального плана постройки дороги.
Требуется написать программу, которая вычислит число возможных планов постройки кольцевой автомобильной дороги с соблюдением указанных требований и найдёт такой план, для которого длина дороги будет минимальной. Гарантируется, что хотя бы один план постройки существует.
Программа получает на вход четыре строки. Каждая из них содержит по два целых числа: \(x_i\) и \(y_i\) — координаты места расположения достопримечательности. Никакие две достопримечательности не находятся в одной точке.
Все числа не превосходят 100 по абсолютной величине.
В первой строке требуется вывести число возможных планов постройки
кольцевой автомобильной дороги. Если таких планов бесконечно много, необходимо вывести
в первой строке выходного файла слово Infinity.
Во второй строке требуется вывести координаты центра дороги минимальной длины и её радиус. Если существует несколько разных способов построения дороги минимальной длины, необходимо вывести координаты центра и радиус любой из них. Координаты центра и радиус должны быть выведены с точностью не хуже \(10^5\) и не должны превышать \(10^9\) . Гарантируется, что существует хотя бы один план с такими параметрами.
| Ввод | Вывод |
|---|---|
0 0 |
7 |
0 0 |
Infinity |
Будем говорить, что для наблюдателя лес является дремучим, если из своего текущего положения наблюдатель видит только деревья. Вам дана карта леса и координаты точки, в которой находится наблюдатель. Требуется определить, кажется ли лес дремучим данному наблюдателю.
На карте леса все деревья изображаются кругами. При этом в лесу бывают сросшиеся деревья (изображения таких деревьев на карте пересекаются), также одно дерево может находиться внутри другого. Точка, в которой стоит наблюдатель, не лежит внутри или на границе ни одного из деревьев.
Программа получает на вход целое число \(N\) — количество деревьев (\(1\le N\le 50000\)). Затем идут два числа, задающих координаты наблюдателя. Затем идет \(N\) троек чисел, задающих деревья. Первые два числа задают координаты центра, а третье — радиус. Все координаты задаются точно, и выражаются вещественными числами не более чем с 2 знаками после десятичной точки, по модулю не превосходящими 100000.
Программа должна вывести строку “YES”, если лес является дремучим, и “NO” иначе. Во втором случае вторая строка выходного файла должна содержать координаты точки, глядя в направлении которой наблюдатель не видит деревьев (то есть луч, вдоль которого смотрит наблюдатель не проходит внутри деревьев и не касается ни одного из деревьев). Координаты нужно вывести не менее, чем с 3 знаками после десятичной точки. Координаты не должны превышать 300000. Расстояние между выданной точкой и наблюдателем должно быть не меньше 1.
| Ввод | Вывод |
|---|---|
4 |
YES |
2 |
NO |
На территории будущей стройки растут три дерева. Фирма получила разрешение на строительные работы с условием, что два (любых) дерева будут сохранены. Прораб хочет построить забор треугольной формы так, чтобы внутри него оказалось ровно два дерева.
Деревья на плане изображаются кругами, которые попарно не вложены друг в друга и не пересекаются (но могут касаться).
Напишите программу, которая по введенной информации о деревьях определит, возможно ли построить такой забор, и, если да, то какое дерево окажется не огорожено.
Программа получает на вход три строки: для каждого дерева координаты центра и радиус круга, изображающего это дерево на плане. Все числа целые, не превосходящие по модулю 3000. Радиус — натуральное число.
Выведите одно число — номер дерева (деревья нумеруются начиная с 1 в порядке задания их во входных данных), которое окажется не огорожено. Если забор треугольной формы, огораживающий ровно два дерева, построить невозможно, выведите число 0. Если существует несколько решений, выведите любое.
| Ввод | Вывод |
|---|---|
0 0 1 |
3 |
При игре в лапту одна команда ловит мяч и пытается осалить им бегущего. Игрок другой команды должен, перед тем как бежать, ударить мяч в поле. Известно, на какое максимальное расстояние он может ударить, а также скорости и начальные координаты игроков другой команды. Требуется выбрать направление и силу удара так, чтобы минимальное время, которое потребуется другой команде, чтобы поднять мяч с земли, было наибольшим. (Пока мяч летит, игроки стоят на местах.)
В первой строке входных данных содержатся два целых числа: \(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 |
9.05539 |
Единственный способ попасть в Зал Круглых Столов — пройти через Колонный Коридор.
Стены Коридора изображаются на карте прямыми линиями, которые параллельны оси 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 |
47 |