Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

5#65796

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

Примечание:

дома могут находиться как по разные стороны пруда, так и поодну;
требуется рассчитать ответ с точностью до десятых (если ответполучился целый, то выводить всегда после запятой один знак);
передвигаться можно только по прямым, но не дугам;
стороны пруда всегда параллельны осям OX и OY;
точки, обозначающие дома могут лежать на границе пруда, и передвигать по границе пруда разрешено.

Формат входных данных
На первой строке подаются параметры пруда через пробел a, x1, y1 (1 <= a <= 1000; -1000 <= x1,y1 <= 1000), где x1,y1 – координаты левого верхнего угла пруда.
На второй строке подаются координаты дома Маши в виде точки xm, ym (-1000 <= xm, ym <= 1000).
На третьей строке подаются координаты дома Саши в виде точки xs, ys (-1000 <= xs, ys <= 1000).
Все числа - целые.
Формат выходных данных
Выведите на одной строке самое кратчайшее расстояние, которое можно пройти от дома Маши к дому Саши. Ответ представляет собой всегда вещественное число с одним знаком после запятой. Если ответ получился больше, то округлить до одного знака после запятой (было 4.5764, стало 4.6).

Элементарная геометрия

✓ 2✗ 191 000средняяВойти и решать

Кладоискатель#60952

Тимофею на день рождения родители подарили металлоискатель. Естественно, наутро мальчик отправился на поиски клада. Он предположил, что когда-то давно кто-то мог обронить золотую монету на древней прямой дороге и для облегчения поиска придумал систему координат. Ось абсцисс OX направлена вдоль дороги, а ось ординат OY направлена вверх.
Устройство работает следующим образом: на его индикаторе выставляется натуральное число r и если ровно на этом расстоянии имеется золотой предмет, то загорается зелёная лампочка.
Сначала юный кладоискатель выставил число r1 в точке x = 0, затем отошёл в точку с абсциссой x = a и выставил число r2, как показано на рисунке. Новичкам везёт, оба раза загорелась зелёная лампочка. Определите координаты потерянной когда-то давно золотой монетки.

Формат входных данных
Программа получает на вход три целых числа a, r1 и r2, записанных в отдельных строках (1 ≤ a, r₁, r₂ ≤ 10⁹ ).
Формат выходных данных
Выведите в двух строках два числа – координаты сокровища (сначала — абсциссу, потом — ординату). Значение ординаты должно быть не положительным (монетка не может висеть в воздухе). Гарантируется, что входные данные таковы, что ответ существует и обе координаты монеты будут целыми числами.

Замечание
Рисунок соответствует примеру из условия.

Вычисление по заданной формуле Элементарная геометрия

✓ 2✗ 21 100средняяВойти и решать

Куда идем мы с Пяточком?#56780

«Кто ходит в гости по утрам, тот поступает мудро…»

Пятачок и Винни-Пух каждое утро ходят пить чай в гости к Кролику. Естественно, самым коротким путем.

К сожалению, однажды Винни-Пуху пришла в голову идея вырыть ловушку для Слонопотама. Самое обидное, что они с Пятачком ее даже вырыли. Поэтому теперь каждое утро, идя в гости к Кролику, они боятся в нее провалиться.

Напишите программу, которая посчитает длину самого короткого безопасного пути от домика Винни-Пуха до домика Кролика.

Ловушка для Слонопотама представляет собой яму абсолютно круглой формы. Путь является безопасным, если он не проходит по ловушке (но может проходить по ее границе).

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

Во входном файле записаны сначала координаты домика Винни-Пуха X_В Y_В, затем — координаты домика Кролика X_К Y_К, а затем — координаты центра и радиус ловушки X_Л Y_Л R_Л. Все координаты — целые числа из диапазона от –32000 до 32000. Радиус ловушки — натуральное число, не превышающее 32000.

Домики Винни-Пуха и Кролика не могут находиться внутри ловушки, но могут находиться на ее границе.

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

Выведите в выходной файл одно число — длину самого короткого безопасного пути от домика Винни-Пуха до домика Кролика с тремя знаками после точки.

Элементарная геометрия

✓ 2✗ 21 000средняяВойти и решать

Собъем воздушный шарик#56739

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

Поскольку Винни Пух очень любит покушать, то в данной задаче (да и не только в задаче) примем его за сферу радиуса P. Центр медведя находится на высоте Hp над уровнем земли. Строго над медведем , находится еще одна сфера, радиуса S – воздушный шарик; центр шарика находится на высоте Hs над уровнем земли. Центры обеих сфер находятся на одной вертикальной прямой. По понятным причинам гарантируется, что сферы не пересекаются J, однако могут касаться.

Считая, что ружье стреляет строго по прямой, вычислите минимальное расстояние L, на которое Пятачок должен отойти от места взлета, чтобы успешно поразить шарик. Шарик считается пораженным, если траектория пули хотя бы касается его поверхности; при этом если траектория пули касается медведя, то он считается невредимым.

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

C клавиатуры вводятся положительные целые числа P, Hp, S и Hs, не превосходящие 10000.

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

Выведите минимальное расстояние от точки взлета, с которого можно поразить шарик из ружья с точностью не менее 5 знаков после запятой.

Элементарная геометрия

✓ 1✗ 91 100средняяВойти и решать

Максимальная площадь#53726

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

Создайте структуру Point и сохраните исходные данные в массиве структур Point.

Входные данные

Программа получает на вход набор точек на плоскости. Сначала задано количество точек n (2<n<101), затем идет последовательность из n строк, каждая из которых содержит два числа: координаты точки. Все исходные координаты – целые числа, не превосходящие 10³.

Выходные данные

Необходимо вывести найденную площадь с точностью в 15 значащих цифр.

Структуры Элементарная геометрия

✓ 5✗ 4800средняяВойти и решать

Максимальный периметр#53723

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

Входные данные

Выходные данные

Необходимо вывести найденный периметр с точностью в 15 значащих цифр.

Элементарная геометрия

✓ 5✗ 4800средняяВойти и решать

Прямоугольники#50551

Петя нарисовал на клетчатом листке бумаги красивый рисунок прямоугольной формы. Его младшему брату Васе тоже захотелось порисовать, поэтому он вырезал из того же листка бумаги другой прямоугольник. При этом он не делал лишних разрезов, то есть в результате в листке осталась прямоугольная дырка. Кроме того, линии разреза не проходили (даже частично) по границам рисунка Пети. Более того, по границам рисунка не проходили даже продолжения линий разреза.

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

Формат входных данных
Вам даны 8 целых чисел - \(x_1, y_1, x_2, y_2, x_3, y_3, x_4, y_4\), где \((x_1, y_1)\) - координаты левого нижнего угла рисунка Пети, \((x_2, y_2)\) - координаты правого верхнего угла рисунка. Аналогично, \((x_3, y_3)\) - координаты левого нижнего угла вырезанного Васей прямоугольника, \((x_4, y_4)\) - координаты правого верхнего угла вырезанного прямоугольника. Гарантируется, что данные прямоугольники невырождены (\(x_1 < x_2\), \(y_1 < y_2\) и аналогичные неравенства для второго набора координат). Листок был не очень большим, поэтому каждое число по модулю не превосходит \(10^4\).

Формат выходных данных
Выведите YES, если Вася испортил рисунок, и NO в противном случае.

Примечание

Вычислительная геометрия Элементарная геометрия

✓ 7✗ 22900средняяВойти и решать

Лазерная пушка#38774

У игрока в космической стрелялке есть очень мощная лазерная пушка. Но она неподвижна и может стрелять только в одном направлении. Игрок может расставить на игровом поле двусторонние зеркала, меняющие ход луча, чтобы поражать врагов. Введём декартову систему координат с центром, где расположена пушка, то есть пушка имеет координаты (0; 0). Пушка стреляет в направлении точки (1; 1). Игрок может поставить зеркала в точках с целочисленными координатами. Зеркала могут быть горизонтальными или вертикальными, попадание луча в зеркало меняет траекторию луча по законам отражения света. Некоторые возможные варианты отражения луча от зеркала изображены на рисунке.

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

Входные данные
Программа получает на вход два целых числа X и Y , не превосходящих по модулю 10000, записанные в разных строках — координаты цели. Точка (X; Y) не совпадает с началом координат.

Выходные данные
Программа должна вывести в первой строке число N — необходимое количество зеркал. Следующие N строк должны содержать информацию о каждом зеркале. В i-й строке должны быть записаны через пробелы два целых числа xi и yi и один символ ti , обозначающие координаты (xi ; yi) точки, в которых установлено i-е зеркало, и тип этого зеркала ti . Если ti является символом «V», то i-е зеркало размещено вертикально, если же ti является символом «H», то зеркало размещено горизонтально. Например, строка «-2 5 H» обозначает горизонтальное зеркало в точке (−2; 5). Зеркала можно выводить в любом порядке. Зеркало нельзя размещать в точке (0; 0), также нельзя размещать два зеркала в одной точке. Значения xi и yi не должны по модулю превосходить 100 000. Также, разумеется, нельзя допустить, чтобы отражённый луч попал в пушку. Если вариантов ответа несколько, выведите любой из них. Если поразить цель в соответствии с условиями задачи невозможно, программа должна вывести одно число «-1». Если для поражения цели зеркала не нужны, программа должна вывести одно число «0»

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 1	1 3 3 H

Задача на реализацию Разбор случаев Элементарная геометрия

✓ 20✗ 1071 000средняяВойти и решать

Сортировка точек#38689

Выведите все исходные точки в порядке возрастания их расстояний от начала координат.

Создайте структуру Point и сохраните исходные данные в массиве структур Point.

Входные данные
Программа получает на вход набор точек на плоскости. Сначала задано количество точек n, затем идет последовательность из n строк, каждая из которых содержит два числа: координаты точки. Величина n не превосходит 100, все исходные координаты – целые числа, не превосходящие 10³.

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

Примеры

№	Входные данные	Выходные данные
1	2 1 2 2 3	1 2 2 3

Использование сортировки Структуры Элементарная геометрия

✓ 5✗ 121 000средняяВойти и решать

Длина дуги#38673

Входные данные
Семь чисел – координаты центра и радиус окружности (возможно, вырожденной) и вещественные координаты двух точек на ней, с точностью до пятого знака после запятой.

Выходные данные
Одно число – длина меньшей дуги окружности, заключённой между указанными точками.

Примеры

№	Входные данные	Выходные данные
1	0 0 1 0 1 1 0	1.57080

Элементарная геометрия

✓ 97✗ 274800средняяВойти и решать

Две окружности#38672

Входные данные
Шесть чисел – координаты центра и радиусы двух окружностей.

Выходные данные
В случае, если количество общих точек окружностей конечно, в первой строке вывести одно число K, равное этому количеству, далее в K строках координаты самих точек. Если указанных точек бесконечно много, вывести единственное число “3”.

Примеры

№	Входные данные	Выходные данные
1	3 4 5 11 4 2	0
2	3 4 5 9 4 2	2 7.75000 5.56125 7.75000 2.43875

Элементарная геометрия

✓ 49✗ 168900средняяВойти и решать

Окружность и прямая#38669

Входные данные
Шесть чисел – координаты центра и радиус окружности и коэффициенты A, B и C нормального уравнения прямой.

Выходные данные
В первой строке одно число K, равное количеству точек пересечения прямой с окружностью. Далее в K строках координаты самих точек.

Примеры

№	Входные данные	Выходные данные
1	2 3 1 1 -1 0	2 3.00000 3.00000 2.00000 2.00000

Элементарная геометрия

✓ 48✗ 296900средняяВойти и решать

Касательная к окружности#38665

Входные данные
Пять чисел – координаты центра и радиус окружности, координаты точки.

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

Примеры

№	Входные данные	Выходные данные
1	2 2 2 2 5	2 0.50929 3.33333 3.49071 3.33333

Элементарная геометрия

✓ 90✗ 315800средняяВойти и решать

Биссектриса#38664

Входные данные
Шесть чисел – координаты точек X, Y и Z.

Выходные данные
Три числа – коэффициенты уравнения биссектрисы угла YXZ.

Примеры

№	Входные данные	Выходные данные
1	0 0 1 0 0 1	1.000000 -1.000000 0.000000
2	0 0 1 3 1 -3	0.000000 -0.632456 0.000000

Элементарная геометрия

✓ 123✗ 428800средняяВойти и решать

Параллелограмм#38551

На уроке геометрии семиклассники Вася и Петя узнали, что такое параллелограмм. На перемене после урока они стали играть в игру: Петя называл координаты четырех точек в произвольном порядке, а Вася должен был ответить, являются ли эти точки вершинами параллелограмма.

Вася, если честно, не очень понял тему про параллелограммы, и ему требуется программа, умеющая правильно отвечать на Петины вопросы.

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

Входные данные
В первой строке входного файла записано целое число N (1 ≤ N ≤ 10) - количество заданных Петей вопросов. Каждая из N последующих строк содержит описание четырех точек - четыре пары целых чисел X и Y (−100 ≤ X ≤ 100, −100 ≤ Y ≤ 100), обозначающих координаты точки.

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

Примеры

№	Входные данные	Выходные данные
1	3 1 1 4 2 3 0 2 3 1 1 5 2 2 3 3 0 0 0 5 1 6 3 1 2	1 3 2 4 0 1 2 3 4

Элементарная геометрия

✓ 71✗ 303900средняяВойти и решать

Целые точки#38432

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

Формат входных данных
В первой строке содержится N (3 ≤N ≤1000) – число вершин многоугольника. В последующих N строках идут координаты (X_i, Y_i) вершин многоугольника в порядке обхода по часовой стрелке. X_i и Y_i - целые числа, по модулю не превосходящие 1000000.

Формат выходных данных
Вывести одно число – искомое число точек.

Примеры

№	Входные данные	Выходные данные
1	4 -1 -1 -1 1 1 1 1 -1	1
2	3 0 0 0 2 2 0	0

Многоугольники. Выпуклые оболочки НОД и алгоритм Евклида Элементарная геометрия

✓ 6✗ 231 100средняяВойти и решать

Сломанный робот#38297

В 2037-м году для создания научно исследовательской базы на Марс высадился отряд роботов, один из которых отправился собирать информацию о районе дислокации. В данный момент роботу из-за отказа некоторых узлов срочно необходимо вернуться в место закладки будущей базы.
Поверхность Марса в районе высадки десанта можно условно представить в виде плоскости с введенной на ней системой координат, такой, что база находится в точке (0, 0). Робот же остановился в точке (x₀, y₀). Он может перемещаться в четырёх направлениях:
• «R» — вправо, при этом координата x робота увеличивается на 1;
• «L» — влево, при этом координата x робота уменьшается на 1;
• «U» — вверх, при этом координата y робота увеличивается на 1;
• «D» — вниз, при этом координата y робота уменьшается на 1.
Из-за неисправности робот не может совершить два перемещения подряд в одном направлении.
Помогите роботу вернуться на базу. Робот должен сделать не более 10000 передвижений, иначе он разрядится и не доедет до базы!

Входные данные
В единственной строке входных данных находятся два целых числа x0 и y0 — изначальные координаты робота (−1000 ≤ x0, y0 ≤ 1000).

Выходные данные
В первой строке выведите целое число, не большее 10000 — количество операций, которые должен сделать робот. Во второй строке выведите сами операции. Каждая операция задаётся одной буквой:
вправо — «R» влево — «L», вверх — «U», вниз — «D». Символы необходимо выводить без пробелов между ними.

Примеры

№	Входные данные	Выходные данные
1	2 1	5 DLULD

Замечание
Вы не обязаны выводить кратчайший маршрут. Например, в приведенном примере кратчайший
маршрут состоит из 3 передвижений: влево, вниз, влево.
Иллюстрация к тесту из примера:

Конструктив Элементарная геометрия

✓ 95✗ 231800средняяВойти и решать

Метеорит#38294

Беда! К городу N приближается метеорит. Людей уже успели эвакуировать, но домам урона не избежать. Ученые уже выяснили, куда упадет метеорит. Вас, как сотрудника страховой компании, попросили выяснить количество домов, которые пострадают при падении метеорита.

Введём на плоскости прямоугольную систему координат. Город представляет собой прямоугольник n × m . Его левый нижний угол расположен в точке с координатами (0, 0) , а правый верхний угол в точке с координатами ( n - 1, m - 1) . В каждой точке с целыми координатами внутри или на границе этого прямоугольника находится дом. Дома в городе N маленькие, поэтому их можно считать точками.

Известно, что метеорит упал в точку ( x , y ) , а радиус его поражения равен r . Таким образом, все дома города на расстоянии не более r от точки падения метеорита получат повреждения. Найдите количество домов, которые получат повреждения.

Входные данные
Первая строка содержит два целых числа n , m ( 1 ≤ n , m ≤ 500 ) — размеры города N.

Вторая строка содержит три целых числа x , y , r ( - 500 ≤ x , y ≤ 500 ; 0 ≤ r ≤ 500 ) — координаты точки падения метеорита и радиус поражения, соответственно.

Выходные данные
Выведите одно число — количество повреждённых домов.

Примечание
Иллюстрация к тесту из примера: чёрными точками обозначены повреждённые дома, белыми — уцелевшие.

Примеры

№	Входные данные	Выходные данные
1	2 3 1 2 1	3

Элементарная геометрия

✓ 31✗ 21900средняяВойти и решать

ASCII-графика#38284

Давным-давно большинство персональных компьютеров были оборудованы видеокартами, работавшими только в текстовом режиме. Если программист хотел изобразить картинку на экране, ему приходилось использовать псевдографику или ASCII-графику. Вот пример картинки, нарисованный с ее помощью:

^..^
(OO)
/  \
()()

Вам дан многоугольник, нарисованный с помощью ASCII-графики. Ваша задача состоит в том, чтобы посчитать количество его сторон.
Картинка состоит из символов ‘.’, ‘\’ и ‘/’. Каждый символ изображает единичный квадрат картинки. Символ ‘.’ обозначает пустой квадрат, символ ‘/’ — квадрат с отрезком из левого нижнего угла в правый верхний, а символ ‘\’ — квадрат с отрезком из левого верхнего угла в правый нижний.

Входные данные
Первая строка входных данных содержит два числа h и w — высота и ширина изображения (2 ? h, w ? 100). Следующие h строк, по w символов в каждой, содержат описание многоугольника, нарисованного с помощью ASCII-графики.
Гарантируется, что картинка содержит ровно один многоугольник, не имеющий самопересечений и самокасаний.

Выходные данные
Выведите одно число — количество сторон многоугольника.

Примеры

№	Входные данные	Выходные данные
1	4 4 /\/\ \../ .\.\ ..\/	8

Задача на реализацию Элементарная геометрия

✓ 2✗ 41 000средняяВойти и решать

три оленя#33114

Однажды на огород к Ивану Петровичу (сыну Деда Мороза и Снегурочки) забежало целых три оленя. Известно, что олени — весьма агрессивное нечто, особенно когда речь идет о борьбе за вкусную зелень. Поэтому каждый из трех оленей, заметив других козлов, замер на месте и начал наблюдать за оставшимися оленями: одним глазом за одним оленем, другим — за оленем номер 2. Естественно, для этого оленю нужно “косить” глазами.

Определите наибольший угол, на который пришлось “раскосить” глазами этим странным животным. Причём тут Иван Петрович и мы, и как олени “раскосили” глаза, мы в душе не знаем. Своего дилера мы не сдадим.

Программа получает на вход координаты трех точек, в которых стоят олени (сначала координаты первого оленя, затем — второго и третьего). Координаты — пара целых чисел, не превосходящих 104 по модулю.

Ввод	Вывод
0 0 3 0 0 4	90.000000

(с) Манаев И., Кашукова М., 2018 г.

Вывод формулы Элементарная геометрия

✓ 7✗ 531 100средняяВойти и решать