Будем говорить, что для наблюдателя лес является дремучим, если из своего текущего положения наблюдатель видит только деревья. Вам дана карта леса и координаты точки, в которой находится наблюдатель.
- На карте леса все деревья изображаются кругами и задаются координатами центра и радиусом
- При этом в лесу бывают сросшиеся деревья (изображения таких деревьев на карте пересекаются),
- Одно дерево может находиться внутри другого.
- Точка, в которой стоит наблюдатель, не лежит внутри или на границе ни одного из деревьев.
- Требуется определить, кажется ли лес дремучим данному наблюдателю.
- Ввод:
строка вида (x0, y0, радиус0), (x1, y1, радиус1), … — карта леса
строка вида 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
Спойлер: эту задачу можно решать многочисленными способами, для меня самый простой оказался такой:
Если хотя бы один не пересекается — с одной стороны у него дерево, а с другой — просвет. Лес не дремучий.