[GCJ] Поливаем цветы!
возможно сначала бинарным поиском находят радиус этой окружности.
нужно научиться проверять для данного радиуса, можно ли в нее впихнуть три другие
нужно научиться проверять для данного радиуса, можно ли в нее впихнуть три другие
Мы уже придумали, как это сделать.
решение в студию тогда!
мммм... а через какие три точки ты проводить собрался?но для окружности вокруг 3-х других окружностей уравнение тоже пишется.
можно заметить, что центр искомой окружности должен находится на пересечении лучей испускаемых из диаметров исходных окружностей (т.к. точка пересечения исходной окружности и искомой - является для обоих окружностей точкой касания).
причем длины испускаемых лучей должны быть равными.
Сега предложил взять 2 радикальные оси между 2 парами окружностей, взять на них по 1 удобной точке вне треугольника, образованного центрами, провести из них внешние касательные к окружностям, построить биссектрисы углов, образованных этими касательными и центр требуемой окружности будет лежать на их пересечении.
Имея возможность строить для 3 окружностей описывающую, находим две самые дальние друг от друга точки (они будут покрываться разными поливалками пусть они лежали на окружностях A и B, фиксируем их, затем перебираем по два круга для A и два для B. Для этой пары троек кругов строим описывающие круги и выбираем среди всех таких пар одну с минимальным радиусом.
Там ещё много надо учесть замечаний, но в целом это весь алгоритм.
Затыком оказалось нахождение описывающей.
П.С. ты попробуй запиши и реши это уравнение...
Имея возможность строить для 3 окружностей описывающую, находим две самые дальние друг от друга точки (они будут покрываться разными поливалками пусть они лежали на окружностях A и B, фиксируем их, затем перебираем по два круга для A и два для B. Для этой пары троек кругов строим описывающие круги и выбираем среди всех таких пар одну с минимальным радиусом.
Там ещё много надо учесть замечаний, но в целом это весь алгоритм.
Затыком оказалось нахождение описывающей.
П.С. ты попробуй запиши и реши это уравнение...
система уравнений в векторной записи
C+R*alpha = C1 + R1*alpha
C+R*beta = C2 + R2*beta
C+R*gamma = C3 + R3*gamma
|alpha|=|beta|=|gamma| = 1
C - центр искомой окружности
C1,C2,C3 - центры исходных
R - радиус искомой
R1,R2,R3 - радиусы исходных
alpha,beta, gamma - единичные векторы параллельные радиусам искомой окружности наложенных на диаметры исходных окружностей
зы
если 4 уравнения спроецировать на оси x и у, то получится 3*2+3=9 уравнений и 9 неизвестных.
либа для решения системы уравнений качается из инета (или, в крайнем случае, открывается конспект лекций)
C+R*alpha = C1 + R1*alpha
C+R*beta = C2 + R2*beta
C+R*gamma = C3 + R3*gamma
|alpha|=|beta|=|gamma| = 1
C - центр искомой окружности
C1,C2,C3 - центры исходных
R - радиус искомой
R1,R2,R3 - радиусы исходных
alpha,beta, gamma - единичные векторы параллельные радиусам искомой окружности наложенных на диаметры исходных окружностей
зы
если 4 уравнения спроецировать на оси x и у, то получится 3*2+3=9 уравнений и 9 неизвестных.
либа для решения системы уравнений качается из инета (или, в крайнем случае, открывается конспект лекций)
для начала уменьшить все окружности на радус меньшей — снижает число писанины.
записать квадратные уравнения для расстояний между центрами окружностей и искомой точкой.
раскрыть и вычесть — должны получится параметрические уравнения двух прямых
...
PROFIT!
записать квадратные уравнения для расстояний между центрами окружностей и искомой точкой.
раскрыть и вычесть — должны получится параметрические уравнения двух прямых
...
PROFIT!
записать три пары квадратных уравнений для расстояний между центрами окружностей и искомой точкой.они не квадратные, а 4-й степени
даже Пифагор знал что ты ошибаешься!
я-то выписывал, в отличие от Пифагора
уравнения будут
![[math]$|O-O_1|+r_1=|O-O_2|+r_2=|O-O_3|+r_3$[/math]](mathimg.php?math=%24%7CO-O_1%7C%2Br_1%3D%7CO-O_2%7C%2Br_2%3D%7CO-O_3%7C%2Br_3%24)
, не?
как их привести к квадратным?
туплю, похоже, понял. Квадратные по R. не, ни хрена не понял
уравнения будут
как их привести к квадратным?
три пары уравнений по координатам
(x_0 - x_i)^2 == (r_0 - r_i)^2
(y_0 - y_i)^2 == (r_0 - r_i)^2
(x_0 - x_i)^2 == (r_0 - r_i)^2
(y_0 - y_i)^2 == (r_0 - r_i)^2
(x_0 - x_i)^2 == (r_0 - r_i)^2что за бред?
(y_0 - y_i)^2 == (r_0 - r_i)^2
верное уравнение — (x_0 - x_i)^2 + (y_0 - y_i)^2 == (r_0 - r_i)^2
ну да, ты меня своей глупостью заразил. или же эта аргентинская косорыловка виновата, хз.
ну да, ты меня своей глупостью заразиля б на лоста скорее грешил
Это ж задача Аполлония. Решается через инверсию.
Решается через инверсию.Ну это классическое решение, построительное. "Через инверсию" — это очень скромная формулировка. Тем более, автору надо программу написать, для этого еще придется овладеть соответствующей техникой (хотя бы два отрезка пересечь — уже будет для него серьезной задачей). Так что идти этим путем не рекомендовал бы. Лучше как посоветовал , что-нибудь вычислительное.
А задачка-то в итоге совсем не так решалась.
Оставить комментарий
agaaaa
Как вычисляется центр окружности, описанной около 3 данных?