Различия между версиями 1 и 4 (по 3 версиям)
⇤ ← Версия 1 от 2021-01-10 00:20:23 →
Размер: 1477
Редактор: FrBrGeorge
Комментарий:
← Версия 4 от 2021-01-13 01:16:39 → ⇥
Размер: 3668
Редактор: FrBrGeorge
Комментарий:
Удаления помечены так. Добавления помечены так.
Строка 3: Строка 3:
Будем говорить, что для наблюдателя лес является дремучим, если из своего текущего положения наблюдатель видит только деревья. Вам дана карта леса и координаты точки, в которой находится наблюдатель. Будем говорить, что для наблюдателя лес является дремучим, если из своего текущего положения наблюдатель видит только деревья. Если набюлюдатель между деревьями видит просвет — лес не дремучий. Вам дана карта леса и координаты точки, в которой находится наблюдатель.
Строка 13: Строка 13:
'''TODO'''
Строка 15: Строка 15:
(587, 597, 100), (361, 239, 103), (320, 543, 114), (845, 296, 117), (260, 335, 93), (228, 616, 117), (119, 128, 107), (121, 640, 85), (575, 261, 87), (640, 581, 100), (448, 361, 99), (254, 579, 115), (718, 257, 114), (441, 653, 114), (450, 588, 94), (222, 619, 119), (647, 668, 78), (686, 422, 85), (249, 446, 104), (746, 219, 80)
577, 441
Строка 18: Строка 20:
YES
}}}

Пример не дремучего леса:

{{{
(607, 250, 31), (579, 469, 32), (606, 270, 19), (172, 319, 24), (128, 159, 28), (244, 110, 29), (616, 374, 37), (470, 173, 44), (468, 658, 25), (648, 652, 38), (811, 212, 20), (284, 579, 8), (910, 452, 42), (242, 361, 26), (70, 654, 37), (173, 329, 26), (206, 536, 11), (208, 620, 50), (352, 83, 6), (543, 498, 9), (949, 663, 49), (452, 273, 50), (84, 71, 22), (692, 688, 25), (67, 269, 10), (586, 118, 8), (558, 488, 42), (611, 149, 11), (982, 494, 24), (61, 660, 6), (543, 167, 43), (695, 152, 11), (830, 473, 42), (427, 89, 42), (207, 413, 31), (466, 736, 15), (639, 475, 28), (357, 699, 41), (347, 650, 26), (747, 111, 27)
448, 422
}}}

{{{
NO
}}}

Спойлер: эту задачу можно решать многочисленными способами, для меня самый простой оказался такой:
{{{#!wiki comment
 * Строим из точки наблюдения лучи-касательные ко всем окружностям (по две штуки)
 * Проверяем, пересекаются ли эти касательные с другими окружностями
 * Если хотя бы один не пересекается — с одной стороны у него дерево, а с другой — ''просвет''. Лес не дремучий.
 * Обратное тоже верно: если просвет есть, он ограничивается именно такими касательными, следовательно, если любая касательная пересекает ещё какую-нидудь окружность, лес дремучий.

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

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

      1. строка вида (x0, y0, радиус0), (x1, y1, радиус1), … — карта леса

      2. строка вида x, y — координаты наблюдателя

    • Вывод: YES (дремучий лес) или NO (не дремучий) 

(587, 597, 100), (361, 239, 103), (320, 543, 114), (845, 296, 117), (260, 335, 93), (228, 616, 117), (119, 128, 107), (121, 640, 85), (575, 261, 87), (640, 581, 100), (448, 361, 99), (254, 579, 115), (718, 257, 114), (441, 653, 114), (450, 588, 94), (222, 619, 119), (647, 668, 78), (686, 422, 85), (249, 446, 104), (746, 219, 80)
577, 441

YES

Пример не дремучего леса: 

(607, 250, 31), (579, 469, 32), (606, 270, 19), (172, 319, 24), (128, 159, 28), (244, 110, 29), (616, 374, 37), (470, 173, 44), (468, 658, 25), (648, 652, 38), (811, 212, 20), (284, 579, 8), (910, 452, 42), (242, 361, 26), (70, 654, 37), (173, 329, 26), (206, 536, 11), (208, 620, 50), (352, 83, 6), (543, 498, 9), (949, 663, 49), (452, 273, 50), (84, 71, 22), (692, 688, 25), (67, 269, 10), (586, 118, 8), (558, 488, 42), (611, 149, 11), (982, 494, 24), (61, 660, 6), (543, 167, 43), (695, 152, 11), (830, 473, 42), (427, 89, 42), (207, 413, 31), (466, 736, 15), (639, 475, 28), (357, 699, 41), (347, 650, 26), (747, 111, 27)
448, 422

NO

Спойлер: эту задачу можно решать многочисленными способами, для меня самый простой оказался такой:

CategoryHomework

LecturesCMC/PythonIntro2020/Homework_DeepWood (последним исправлял пользователь FrBrGeorge 2021-01-13 01:16:39)