Модуль: Бинарный поиск. Практика

Бинарный поиск применяется для решения широкого класса задач и  способы его реализации бывают разные. 
Рассмотрим следующую задачу.
Необходимо найти точку пересечения отрезка AB и сферы радиуса R, с центром в точке O 
(Гарантируется, что внутри сферы находится только одна из границ отрезка. Будем считать, что внутри сферы точка A).
Можно, конечно, найти аналитическое решение, но 

• во-первых, что даст знание координат точки пересечения?
• во-вторых, аналитическое решение ещё надо реализовать

• проверка на то, что точка лежит внутри сферы с заданным центром и радиусом тривиальна
• точки на отрезке можно задавать с помощью отношени (рациональной дроби)
• точность вычислений определять "числом шагов" бинарного поиска.

1. Программа check(T, O,r)  возвращает 1 если точка T лежит внутри сферы или на сфере, в противном случает возвращает 0
   T, O - кортежи  из трех координат каждый
   r - положительное вещественное число
   правило проверки \((T_x-O_x)^2 +(T_y-O_y)^2 +(T_z-O_z)^2 \leq r^2\) 
2. Программа next_dot(L,R) - возвращает коэффициенты разбиения AB для "средней точки" (M) 
   L, R - коэффициенты "левой" и "правой" границ отрезка (L < R). Коэффициент \(k\ (0\leq k \leq1) \) - определяет точку T на \(\overline {AB}\) "векторным способом \(\overrightarrow{OT} = \overrightarrow{OA} + k\cdot\overrightarrow{AB}\)
   Для практических целей было бы удобно, чтобы k были бы ращиональными дробями. Поэтому задавать парами чисел (числитель, знаменатель)
   Начальными значениями можно считать L = (0,1), R =(1,1) (то есть 0 и 1). Новое значение M можно получать как  (L[0] + R[0], L[1] + R[1] ) .
   (нетрудно проверить, что для натуральных \(a,b,c,d \ из\ \frac{a}{b}<\frac{c}{d} =>\frac{a}{b}<\frac{a+c}{b+d}<\frac{c}{d} \))
   Если \(k = \frac{n}{m}\) - коэффициент разбиения отрезка AB, то координаты точки разбиения есть \((A_x+(B_x-A_x)\cdot\frac{n}{m},A_y+(B_y-A_y)\cdot\frac{n}{m},A_z+(B_z-A_z)\cdot\frac{n}{m})\)
3.  Вопрос "достоверности"/точности можно решить заданием количества шагов разбиений или ограниченим на значение знаменателя дроби разбиения.