<ПРЕД Задача:
СЛЕД>
Задачу решили 22 пользователя: greck, mishik, WsemirZ, dan, mazahaka, zloy_mipt, UdH-WiNGeR, ilyakor, tourist, defrager, abortmozga.ru, DAV, MIKseR, Algeran, Lu, TonyZH, ZhanibekDATBAEV, ripatti, Dest, vi002, regmar, avg79.
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Лучшая кластеризация

Time limit = 20 секунд(ы)

Memory limit = 128000

Задача о кластеризации может быть сформулирована следующим образом:

ЗАДАЧА. Дано некоторое множество S точек в трёхмерном евклидовом пространстве. Разбейте это множество на непересекающиеся подмножества (кластеры) S1, S2, ..., SK, так, чтобы величина D была минимальна:

При этом в каждом из подмножеств Si должно быть более одной точки, то есть размеры множеств ni = |Si| ≥ 2.

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

Для каждого теста t есть критическая величина D0(t). Если кластеризация, предложенная вашей программой, имеет D < D0(t), то тест t считается пройденным.

Чем меньше величина D для разбиения, найденного вашей программой, тем больше баллов она получит. Баллы, заработанные вашей программой в случае прохождения всех тестов считаются следующим образом:

Вход В первой строчке входа дано количество точек N, N ≤ 5000. В следующих N строчках находятся тройки вещественных чисел < 2 000 000 по модулю.

Выход Выведите число кластеров С и затем N строчек, в каждой из которых находится номер кластера, которому принадлежит соответствующая по порядку точка во входных данных.

Вход#1
2
1 1 1
3 -3 3
Выход#1
1
1
1
Вход#2
6
101.123 100.123 99.123
100.123 99.123 99.123
0.123 0.123 -0.123
0.123 -0.123 0.123
-0.123 0.123 0.123
100.321 100.123 100.123
Выход#2
2
1
1
2
2
2
1

Автор:
Ворожцов Артем
4 августа, 2003

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 200ms

SW soft NIX
ID = 3.234.245.121