Вписать в четырехугольник два непересекающихся круга

[Alexunder2]

Здравствуйте!

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

Какие идеи можно применить?

PS. Задача, вообще говоря, по программированию, с кодингом проблем нет, но вот саму идею найти поймать не могу :(

[gris]

Слово "вписать" в сугубо геометрическом смысле означает расположить круг так, чтобы он касался всех сторон четырёхугольника. Это можно сделать не более, чем одним способом, насколько я представляю.
Вероятно, имеется в виду расположить во внутренней области четырёхугольника два непересекающихся круга с максимальной суммой радиусов. Скорее всего они будут касаться друх друга (непересечение, конечно, относится к внутренностям кругов) и каких-то сторон.
То есть вот такая картинка?

[Alexunder2]

ну да, смысл такой :)
В какую сторону смотреть?))

[Sonic86]

Блин, я что-то затрудняюсь...
Можно сделать так. Перебирать углы 4-х угольника для каждого круга (всего $4^2=16$ пар) и в каждый угол вписывать круг так, чтобы радиус был максимальный, вписывать сначала 1-й круг, а потом 2-й (только вот я не уверен, что при этом способе сумма радиусов будет всегда максимальна), но при этом надо еще умудриться определить координаты второго центра так, чтобы круги касались. Это можно численно сделать (это несложно должно быть) или подумать еще.... Потом из 16 вариантов выбрать лучший...

[ИСН]

Факт, прежде чем кодить, тут будет много кропотливого разгребания математики.

-- Чт, 2011-04-14, 15:33 --

В частности, перебор прост, если максимум всегда реализуется на такой конфигурации: один круг зажат между тремя сторонами, второй - между ним и какими-то двумя соседними. Ну, как вот на картинке. Всегда так будет?
Хрен-то!

[gris]

Но для выпуклых четырёхугольников круги точно будут соприкасаться (или их можно так сдвинуть без ущерба, как в случае вытянутого прямоугольника). То есть нужно максимизировать расстояние между центрами кругов.

[Sasha2]

gris в сообщении #434739 писал(а):

Но для выпуклых четырёхугольников круги точно будут соприкасаться (или их можно так сдвинуть без ущерба, как в случае вытянутого прямоугольника). То есть нужно максимизировать расстояние между центрами кругов.

Это возможно только в том случае, когда диагональ данного четырехугольника является биссектрисой двух противоположных углов, поэтому в общем случае скорее две данные окружности не смогут коснуться друг друга.

[gris]

А что нам мешает сдвинуть одну из окружностей к другой? Я имел в виду выпуклые 4угольники

[Sasha2]

Да это я неподумавши написал.
Но все равно задача поставлена весьма расплывчато.
На рисунке например показано, что одна окружность касается трех сторон, а друга двух.
Совсем не факт, что это расположение реализует решение. Может быть решением являются две окружности, вписанные в какие-либо два угла. Кроме того, совершенно непонятно, почему, например, такими окружностями не могут быть такие две, из которых одна касается только лишь одной из сторон.

[ИСН]

Sasha2 в сообщении #434768 писал(а):

Кроме того, совершенно непонятно, почему, например, такими окружностями не могут быть такие две, из которых одна касается только лишь одной из сторон.

Нет, это-то как раз понятно. Её можно, если так, сдвинуть и увеличить, потом ещё, и так пока она не упрётся во что-нибудь.
Но вопросов пока что довольно много.

[gris]

Удивительно, что для квадрата программа сочла, что решений много. То есть центы всех кругов подобного (см на рис.) расположения находятся на одинаковом расстоянии друг от друга.