Точки в прямоугольнике , Задача на максимум

Вводится три числа: A, B, N. (A, B - действительные числа, N - целое больше 2)
Надо расположить в прямоугольнике AxB N точек так, чтобы суммарное расстояние между каждыми двумя точками было бы максимальным.
Для примера, если A = 10, B = 5 и N = 2, то точки можно расположить в (0, 0) и (10, 5).
Если 4 точки, то они размещаются в вершинах прямоугольника.

самый большой обход по периметру ?

По-моему, вообще все точки в углах надо поставить В как можно более противоположных Ну может одну еще в центре... Хотя нафих она там нужна

Сообщение отредактировано: Visitor - 21.11.03, 16:08

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

зачем думать, когда можно численно оптимизировать??

ИМХО все равно расставлять надо буквой "зю" -- верхлев-нижправ-нижлев-верхправ-верхлев-нижправ и т.д.

интерестная задача. из серии максимизации фукнционала.
можно так сделать:
написать прогу, которая будет для заданных парамов перебирать все возможные положения точек (с некоторым шагом) и выдавать оптимальное расположения.
посмотреть эти расположения на 2, 3, 4, 5, ... n точек и сделать вывод о тенденции (если она будет)

а чойто за буква?

ага, перебирать все расположения!! имхо моё предложение будет в етом смысле получше
можно отталкиваться не по кулону, а высчитывать градиент етого функционала. кстати функционал будет с корнями, так что аналитически врядли можно решить

Да, интересная, олимпиадная.
Идея wormball-а интересная и весьма перспективная, только как ее реализовать?
И не получится ли это "жадное" решение?

Тогда приближенно! Вообще, в каую сторону копать-то?

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

dx=dt*vx всмысле x[i]:=x[i]+vx[i]*dt для всех i, dt - временной шаг
dy=dt*vy

dvx=dt*((dF/dx)-k*vx) k - коеффициент трения
dvy=dt*((dF/dy)-k*vy)

отталкиваться от стенок я думаю понятно как.

производную функционала сам найдёшь??

Постараюсь. В принципе, все понятно. Если что, спрошу конкретнее.