Вписанные окружности, программирование? Опции

[UNDEFEAT]

Есть вот такая задача:


Задача решена, но в решении использовался метод "подбора" решения бинарным поиском.
Вопрос в следующем: имеет ли эта задача аналитическое решение в общем случае?
Буду признателен, если кто-то поделится своими мыслями по этому поводу.

Вот вкратце идея программы:
Отрезки проведённые из центров соседних окружностей к точке их касания лежат на одной прямой. Значит из них получается многоугольник с вершинами в центрах окружностей. Пусть Ri - искомые расстояния, а R - радиус вписанной в многоугольник окружности, тогда:
R1^2 - r1^2 = R2^2 - r2^2 = ... = Rk^2 - rk^2 = R^2
Пусть величина угла AiOAi+1 равна fi, тогда:
f1 + f2 + ... + fk = 2*pi
Также:
fi = 2 * arctg(ri / R).

Итого, бинарным поиском мы можем найти такое R, что сумма углов будет равняться 2*pi. Зная R мы найдём все Ri.


Аналитически вроде это решить нельзя...

Сообщение было отредактировано UNDEFEAT: 21.3.2016, 2:06

[alan]

Разве имей задача аналитическое решение она бы могла стать задачей по программированию?

[UNDEFEAT]

Разве имей задача аналитическое решение она бы могла стать задачей по программированию?

Естественно! Таких море.
Просто даже решив математическую задачу аналитически бывает довольно сложно научить компьютер быстро выдавать ответ. А иногда не решив задачу аналитически в принципе не возможно быстро выдать ответ

Сообщение было отредактировано UNDEFEAT: 21.3.2016, 2:19

[VitalyKolobkov]

Я что-то вообще не понимаю, в чем проблема. Если нам изначально заданы углы а_1, а_2, а_k, и радиусы r_1, r_2, .. r_k, то из касания окружностей имеем
r_1/tan(a_1/2)=r_2/tan(a_2/2)...=r_k/tan(a_k/2)
но тогда
R_1=r_1/sin(a_1/2)
R_2=r_2/sin(a_2/2)
...
R_k=r_k/sin(a_k/2)

[UNDEFEAT]

Я что-то вообще не понимаю, в чем проблема. Если нам изначально заданы углы а_1, а_2, а_k, и радиусы r_1, r_2, .. r_k, то из касания окружностей имеем
r_1/tan(a_1/2)=r_2/tan(a_2/2)...=r_k/tan(a_k/2)
но тогда
R_1=r_1/sin(a_1/2)
R_2=r_2/sin(a_2/2)
...
R_k=r_k/sin(a_k/2)

Но ведь углы не заданы.
Заданы радиусы окружностей.
Если бы был задан хотя бы один угол, вопросов никаких бы не было

Сообщение было отредактировано UNDEFEAT: 22.3.2016, 8:42

[VitalyKolobkov]

Но ведь углы не заданы.
Заданы радиусы окружностей.
Если бы был задан хотя бы один угол, вопросов никаких бы не было

Тогда такое ощущение, что никак, потому что к выражению
f1 + f2 + ... + fk = 2*pi
можно применить тангенс, после чего получится алгебраическое уравнение на R порядка k, которое будет зависеть от всех r_k, причем весьма красивым и симметричным образом. Как известно, алгебраическое уравнение степени выше 4 не разрешимо в радикалах в общем случае. Конечно же, коэффициенты этого уравнения будут далеко не произольными числами, но я почти уверен, что это будет эквивалентно общему случаю.

[UNDEFEAT]

Тогда такое ощущение, что никак, потому что к выражению
f1 + f2 + ... + fk = 2*pi
можно применить тангенс, после чего получится алгебраическое уравнение на R порядка k

Вообще, там получится уравнение вида:
P(x) * Q(x) / R(x) = 0
где х - вектор (r1/R, r2/R, ..., rk/R), P(x) имеет степень k, Q(x) имеет степень k-1, а R(x) имеет степень 2k-1.
Так что пока всё совсем не очевидно.