Вітання. Прошу допомоги. Загалом завдання: на координатної площині задається відрізок з початком в точці А і з кінцем в точці В. Також задаються кола (можна і 1 коло) з центрами в точках M1, M2, M3. M100 і з радіусами R1, R2, R3. R100. Потрібно перевірити, чи належить будь-яка точка відрізка заданої (заданим) колах.
В общем-то програма працює, але, ймовірно, не завжди правильно. Вже досить багато перепробував тестових прикладом, все правильно визначає. Але, коли відправляю рішення на сервер олімпіади, сервер каже: "Wrong Answer". Я все грішу на типи. Чи зможете допомогти?
На малюнку зображені два випадки неперетинання відрізком окружності:
- Коли пряма не перетинає окружність.
- Коли пряма перетинає коло, а відрізок не перетинає.
Для кожного кола (R, M) і відрізка AB можна застосувати наступний алгоритм:
- Обчислюємо коефіцієнти рівняння
(A + qB) / (1 + q) on (R, M). або
(Xa + q * xb - (1 + q) * xm) 2 + (ya + q * yb - (1 + q) * ym) 2 = (1 + q) 2 * R 2:
С2 q 2 + 2C1 q + C0 = 0, де
C0 = (xa - xm) 2 + (ya - ym) 2 - R 2,
C1 = (xa - xm) * (xb - xm) + (ya - ym) * (yb - ym) - R 2,
C2 = (xb - xm) 2 + (yb - ym) 2 - R 2. - якщо C0 <= 0, точка A попала в круг.
- якщо C2 <= 0, точка B попала в круг.
- Якщо det = C1 2 - C0 C2 <= 0, прямая АB с кругом не пересекается.
- Обчислюємо коріння рівняння q1 і q2 (якщо є).
- Якщо q1> = 0 АБО q2> = 0. то потрапили. Інакше не потрапили.