Алгоритм Ллойда по правилам
Выполните алгоритм Ллойда для точек на плоскости с заданными начальными центрами. Чтобы ответ был единственным, правила строгие:
- Шаг «отнести»: каждая точка относится к центру с наименьшим квадратом евклидова расстояния; при равенстве — к центру с меньшим номером.
- Если разбиение не изменилось по сравнению с предыдущим шагом, алгоритм останавливается (на самом первом шаге «предыдущего» разбиения нет, и он всегда считается изменившим что-то).
- Шаг «пересчитать»: каждый центр переносится в среднее арифметическое своих точек. Центр, к которому не отнесено ни одной точки, остаётся на месте.
- Пара шагов «отнести + пересчитать» — одна итерация; итераций не больше t.
Вход
В первой строке n, k, t (1 ≤ n ≤ 1000, 1 ≤ k ≤ 10, 1 ≤ t ≤ 100). Дальше n строк с целыми координатами точек, потом k строк с целыми координатами начальных центров. Координаты по модулю не больше 10⁴.
Выход
В первой строке — число выполненных итераций (сколько раз центры пересчитывались). Дальше k строк — итоговые центры. В последней строке — итоговая инерция: сумма по всем точкам квадрата расстояния до ближайшего из итоговых центров. Дробные числа проверяются с погрешностью 10⁻⁶.
Примеры
Пример 1
12 3 100 1 1 2 2 2 1 3 2 8 8 9 10 9 7 8 9 1 8 2 9 2 10 3 8 1 1 2 2 2 1
2 1.000000 1.000000 5.250000 8.625000 2.333333 1.666667 96.708333
Ограничения
- Время · Python
- 6000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 8 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
В статье код уже есть — проверьте, что он делает с пустой группой и с равными расстояниями. Что требует условие?
2Идея
Это ровно алгоритм из статьи, без всякой оптимизации: n·k ≤ 10 000 сравнений на итерацию, сто итераций — миллион операций. Вся трудность — в правилах: они делают результат единственным, а значит, проверяемым. В настоящих библиотеках их тоже приходится выбирать, и разные библиотеки выбирают по-разному.
3Разбор
Храним метки предыдущей итерации (сначала их нет). На каждой итерации считаем новые метки, перебирая центры по порядку и обновляя лучший только при строго меньшем расстоянии — так ничья достаётся меньшему номеру. Если новые метки совпали со старыми — выходим, не увеличивая счётчик. Иначе запоминаем метки, увеличиваем счётчик и пересчитываем центры по суммам; центр без точек не трогаем.
После цикла считаем инерцию заново от итоговых центров: каждая точка — до ближайшего из них. Обратите внимание на тест с лимитом t = 1: после одной итерации алгоритм ещё не сошёлся, и метки, по которым были посчитаны центры, уже не соответствуют самим центрам. Поэтому инерцию считаем от расстояний, а не по старым меткам.
3+Решение
4Сложность
O(t·n·k) времени, O(n + k) памяти.
5Типичные ошибки
- Пустой центр в ноль. Деление на ноль обходят, сбрасывая центр в (0, 0) или удаляя его, — но условие велит оставить центр на месте. Третий тест ставит один центр за тысячу единиц от всех точек.
- Счётчик итераций. Итерация, на которой метки не изменились, не считается: центры не пересчитывались.
- Инерция по старым меткам. Неверна, когда алгоритм остановлен лимитом t.