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

7 задач
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Ускорители для Деда Мороза#44037

Дед Мороз за ночь должен посетить N городов. У него есть двумерный план расположения всех городов. План нарисован в декартовой системе координат, в которой точкой (0, 0) обозначено место старта Деда Мороза. Каждый город на плане отмечен точкой с координатой (Xi, Yi). Также на карте обозначены M точек с координатами (Pi, Qi), в которых расположены ускорители. Чтобы успеть разнести все подарки, Дед Мороз может воспользоваться ускорителем, который увеличивает его скорость в два раза (а может им и не пользоваться).

Дед Мороз в Новогоднюю ночь начинает с места старта, посещает все N городов и возвращается обратно.

Начальная скорость Деда Мороза равна 1. Найдите наименьшее время, необходимое Деду Морозу, чтобы посетить все города и вернуться обратно. Временем, при котором он раскладывает все подарки будем пренебрегать!



Входные данные
Первая строка входных данных содержит два целых числа N и M (1 <= N <= 12, 0 <= M <=5). Следующие N строк содержат координаты городов (Xi, Yi). Далее идут M строк с координатами ускорителей (Pi, Qi). Все координаты различны и среди них нет координаты (0, 0).

Выходные данные
Выведите ответ на задачу, с точностью не менее 6 знаков после запятой.
 
 
Примеры
№ Входные данные Выходные данные Примечание
1 2 1
1 1
0 1
1 0		 2 1
1 1
0 1
1 0		 Вот один из оптимальных способов разнести все подарки
  • Пройти расстояние 1 от начала координат до ускорителя 1 со скоростью 1, затратив время 1.
  • Пройти расстояние 1 от ускорителя 1 до города 1 со скоростью 2, затратив время 0,5.
  • Пройти расстояние 1 от города 1 до города 2 со скоростью 2, затратив время 0,5.
  • Пройти расстояние 1 от города 2 до начала координат со скоростью 2, затратив время 0,5.
2 2 1
1 1
0 1
100 0		 3.4142135624 Вот один из оптимальных способов разнести все подарки
  • Пройти расстояние 1.41... от начала координат до города 1 со скоростью 1, затратив время 1.41....
  • Пройти расстояние 1 от города 1 до города 2 со скоростью 1, затратив время 1.
  • Пройти расстояние 1 от города 2 до начала координат со скоростью 1, затратив время 1.
3 1 2
4 4
1 0
0 1		 4.3713203436 Вот один из оптимальных способов разнести все подарки
  • Пройти расстояние 1 от начала координат до ускорителя 1 со скоростью 1, затратив время 1.
  • Пройти расстояние 1,41... от ускорителя 1 до ускорителя 2 со скоростью 2, затратив время 0,707....
  • Пройти расстояние 5 от ускорителя 2 до города 1 со скоростью 4, затратив время 1,25.
  • Пройти расстояние 5,65... от города 1 до начала координат со скоростью 4, затратив время 1,41....
Алгоритмы на графахДинамическое программирование на таблицахЭлементарная геометрия
✓ 2✗ 181 300средняяВойти и решать
Дремучий лес#38361
Просека — эта такая прямая линия, которая проходит через лес (то есть деревья есть как с одной стороны от этой линии, так и с другой), и при этом она не проходит ни через одно из деревьев леса, а также не касается деревьев. Будем говорить, что лес является дремучим, если в нем нет ни одной просеки.

На плане леса все деревья изображаются кругами. Никакие два круга не пересекаются и не касаются друг друга. Требуется по этому плану определить, является ли лес дремучим.

Входные данные
Во входном файле содержится сначала целое число N — количество деревьев (1 ≤ N ≤ 200). Затем идет N троек чисел, задающих деревья. Первые два числа задают координаты центра, а третье — радиус. Все данные задаются точно, и выражаются вещественными числами, не более чем с 2 знаками после десятичной точки, по модулю не превосходящими 1000.

Выходные данные
В первой строке выходного файла должно содержаться сообщение YES, если лес является дремучим, и NO иначе. Во втором случае вторая строка выходного файла должна содержать координаты двух точек, через которые проходит просека. Все координаты нужно выводить с восемью знаками после десятичной точки, координаты не должны превышать 2000, и расстояние между выданными точками должно быть не меньше 100.
 
Примеры
№ Входные данные Выходные данные
1 3
 0.00 30.00 25.00
 0.00 -30.00 25.00
 40.00 0.00 16.00		 NO
-833.3333340000 -552.7707973875
 833.3333340000 552.7707973875
2 3
0.00 30.00 29.00
0.00 -30.00 29.00
40.00 0.00 19.00		 YES
Элементарная геометрия
✓ 2✗ 61 200средняяВойти и решать
Посчитайте лампы#38348
На новой станции метро, которую планируют открыть в конце этого года, будет N эскалаторов (эскалаторы пронумерованы подряд числами от 1 до N). Эскалаторы имеют длину L и расположены на расстоянии H друг от друга. Шириной эскалатором пренебрежем. Между каждыми двумя соседними эскалаторами (точно посередине) будет установлен ряд ламп. В ряду будет K ламп. Лампы устанавливаются по следующему принципу: всю длину эскалатора L разбивают на K равных отрезков и в середине каждого отрезка устанавливают по лампе (см. рисунок). Всего будет установлено (N–1)*K ламп.


На приведенном рисунке N=4 (эскалаторы показаны жирными <горизонтальными линиями), L=20, H=4, K=5.

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

Входные данные
Во входном файле записаны числа N, L, H, K, J. Все числа — натуральные. 2≤N≤35, 1≤L≤1000, 1≤H≤1000, 1≤K≤35, 1≤J≤N.

Выходные данные
В выходной файл выведите одно число — ответ задачи.
Примеры
№ Входные данные Выходные данные
1 2 20 4 5 1 0
2 4 20 4 5 2 11
Элементарная геометрия
✓ 2✗ 21 300средняяВойти и решать
Вася с пультом#33116
Однажды, Вася взял без спроса у бабушки пульт от телевизора и выбежал во двор с прямого хода. Радиус двора - R метров. Прямой путь от парадного выхода до калитки - хорда AB, являющаяся диаметром этой окружности. Добежав до центра окружности, он увидел деда выскочившего ему наперерез. Василий принял решение сбежать через дырку в заборе. Но чтобы не портить бабушкины цветы и тем самым не добить её своим поступком, он подумал что лучше всего бежать по дорожкам. На картинке они обозначены.


Близжайщая тропинка ведущая до дырки - AC, к ней от центра ведёт дорожка ОН. 
 
Подсчитайте расстояние которое ему предстоит пробежать c момента как он выскочил из дома.
1 < R < AC < 10^18

Входные данные:
10 16
Выходные данные
24.000

(с) Медведев Д., 2018
Вычисление по заданной формулеЭлементарная геометрия
✓ 0✗ 11 200средняяВойти и решать
*Лапта#25963

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


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

- в первой строке входных данных содержатся два числа: D — максимальное расстояние удара и N — количество соперников на поле (D и N натуральные числа, \(D <= 1000\), \(N <= 200\)); 
- в следующих N строках задается по три числа – начальные координаты xi и yi и максимальная скорость vi соответствующего игрока (скорости и координаты — целые числа, \(–1000 <= x_i <= 1000\), \(0 <= y_i <= 1000\), \(0 < v_i <= 1000\)).
Никакие два игрока не находятся изначально в одной точке. Игрок, бьющий мяч, находится в точке с координатами (0,0). Мяч выбивается в точку с неотрицательной ординатой (\(y >=  0\)).


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

Примеры
№ Входные данные Выходные данные
1
10 2
1 1 1
-1 1 1
9.05539
0.00000 10.00000
Бинарный поиск по ответуКвадродеревоЭлементарная геометрия
✓ 7✗ 781 400средняяВойти и решать
Идеальный сад#22026
Один успешный бизнесмен Василий после двух долгих лет непрерывной работы ушел в долгожданный отпуск. Желая расслабиться, у него 
возникла идея завести сад из синих и красных цветов на заднем дворе своего коттеджа. Ежедневная работа с таблицами ему изрядно надоела, 
поэтому он хотел видеть сад круглой формы. Однако чтобы созерцание сада, сидя на кресле, было максимально расслабляющим, 
граница между синими и красными должна быть на одинаковом расстоянии L от него. 
 
Василий нанял садовника для создания сада. Садовник закупил одинаковое количество красных и синих цветов, Но потом вспомнил последнее 
условие бизнесмена. Ему было жаль выкидывать так много цветов, поэтому он решил что граница между разными цветами должна делить сад 
на две равные по площади части. Тогда он сможет посадить все цветы. Не владея высокими знаниями геометрии, садовник смог посчитать 
радиус сада R, но расстояние от кресла на веранде до центра сада он попросил посчитать Вас. 
 
Входной файл содержит целое число R - радиус сада (1 < R < 10000) и целое число L - расстояние от кресла до границы между синими и красными 
цветами (1 < L < 10000). Ваша задача вывести расстояние от кресла на веранде до центра сада. Ответ округлите до сотых, или выведите -1, 
если построить такой сад невозможно. Обратите внимание, что кресло может находится как за пределами сада, так и в саду. 

Входные данные: 
12 15 
 
Выходные данные: 
13.262 
 
 
Входные данные: 
100 1 
 
Выходные данные: 
-1 


(с) Линд Владимир
Вывод формулыЭлементарная геометрия
1 300средняяВойти и решать
Поделиться
Класснуть