Распределение множества точек на 2 подмножества.

[wovas]

Итак, друзья, помогите решить такую задачу.
На плоскости расположено N<=1000 точек и заданы растаяния между любыми двумя.
Нужно разбить эти точки на два подмножества. При этом в этих подмножествах будут максимальные расстаяния между какими-то точками их длины: max1 и max2. Дефектом разбиения назовём |max1-max2|.
Нужно найти такое разбиение, чтобы дефект был минимальным.

Если у Вас есть предложения, решения, или хотя бы мысли по теме - поделитесь пожалуйста. Очень надо, лаба горит.

Добавлено спустя 2 часа 37 минут 37 секунд:

Спасибо тем, кто думал. Кому интересно смотрите
Задача про сад и деревья.
http://uoi.kiev.ua/Download.aspx?name=UOI\2007\article.zip
Сори за проблемы с линком, но как я понимаю просто надо копироватьстроку адреса, так как "\" не входят в стандарты URL, а спецификация ASP. Я не спец могу ошибаться.

[IlyaLevchenko]

1. Отсортируй по убыванию этот массив на 1 млн расстояний.
2. Возьми два максимальных расстояния сверху, но так, чтобы эти пары точек были различными.
3. Добавь оставшиеся точки к любой из этих родительских пар.

Все что не так прошу отнести к неясной постановке задачи

PS Твой линк не работает.

[wovas]

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

[photon]

Эта тема имеет непосредственное отношение к вашей работе, но там задача немножко сложнее