Аглебра и Геометрия

[Гость]

Помогите решить
На наблюдаемой местности расположено N круглых ям с координатами (xi; ;yi), диаметрами di (i=0..N) Для объекта, движущегося в направлении вектора w=(a,b) из точки Е=Т(x,y);
г) Определить, какое количество ям встретится у него на пути.
Входные данные:
 целое положительное число N (N<50);
 N строк вида xi, yi, di, где xi , yi — координаты центра ямы, di – диаметр;
 Числа a и b — координаты направляющего вектора движения объекта, x, y- координаты точки отправления.
Выходные данные:
 Целое число K – количество ям, встречающихся на пути объекта.

[Гость]

Для каждой ямы из списка (i = 0..N) делаем 4 простых шага:Шаг 1: Радиус ямыНаходим радиус R из диаметра d:R = d / 2Шаг 2: Проверка «Впереди или сзади?» (Скалярное произведение)Проверяем, не осталась ли яма позади точки старта E. Для этого считаем число S:S = a * (xi - x) + b * (yi - y)Если S < 0, яма осталась сзади. Объект её не встретит. Переходим к следующей яме.Если S >= 0, яма впереди. Считаем дальше.Шаг 3: Расстояние до линии путиСчитаем квадрат расстояния L2 от центра ямы (xi, yi) до луча движения:L2 = (b * (xi - x) - a * (yi - y))^2 / (a^2 + b^2)Шаг 4: Финальное решение по ямеСравниваем квадрат расстояния L2 с квадратом радиуса R^2:Если L2 <= R^2, объект пересечёт эту яму! Прибавляем 1 к общему счётчику K.Если L2 > R^2, объект пролетит мимо.шт

[Гость]

Для каждой ямы из списка (i = 0..N) делаем 4 простых шага:Шаг 1: Радиус ямыНаходим радиус R из диаметра d:R = d / 2Шаг 2: Проверка «Впереди или сзади?» (Скалярное произведение)Проверяем, не осталась ли яма позади точки старта E. Для этого считаем число S:S = a * (xi - x) + b * (yi - y)Если S < 0, яма осталась сзади. Объект её не встретит. Переходим к следующей яме.Если S >= 0, яма впереди. Считаем дальше.Шаг 3: Расстояние до линии путиСчитаем квадрат расстояния L2 от центра ямы (xi, yi) до луча движения:L2 = (b * (xi - x) - a * (yi - y))^2 / (a^2 + b^2)Шаг 4: Финальное решение по ямеСравниваем квадрат расстояния L2 с квадратом радиуса R^2:Если L2 <= R^2, объект пересечёт эту яму! Прибавляем 1 к общему счётчику K.Если L2 > R^2, объект пролетит мимо.

[admin]

Пусть R = di/2, dx = xi - x, dy = yi - y (E = (x,y) — старт, w = (a,b) — направление).

1) S = a*dx + b*dy. Если S >= 0, яма впереди и пересекается тогда, когда (b*dx - a*dy)^2 <= R^2*(a^2 + b^2).
2) Если S < 0, центр ямы сзади, но яму всё равно надо засчитать, когда старт лежит внутри неё: dx^2 + dy^2 <= R^2.

K — количество ям, для которых выполнено 1) или 2). Всё считается в целых/квадратах, без корней и деления.