Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1838. Компьютерное зрение
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 06/10/2012 | Личное первенство Южного Урала (A) |
Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Одной из основных задач компьютерного зрения является построение модели
скелета человека по данным, полученным от различных
устройств (RGB-камеры, IR-сенсора и т.д.). В большинстве случаев в качестве данных
используются карты глубин – структуры,
описывающие расстояния от устройства до точек сцены. В нашем случае карты глубин
представлены прямоугольными числовыми матрицами.
Каждый элемент матрицы (пиксел) соответствует некоторой точке в пространстве
сцены (в нашей задаче для простоты используется
ортогональная проекция на картинную плоскость), множество таких точек
будем называть облаком точек (см. рисунок). Облако точек,
представляющих человека в сцене, будем называть облаком точек человека.
Одним из методов скелетизации является метод Voxel Scooping. В ходе его применения
возникает следующая подзадача: необходимо разделить
облако точек человека набором плоскостей, параллельных картинной
таким образом, чтобы точки облака были наиболее равномерно
распределены в областях, порождаемых разбиением.
Итак, дана прямоугольная матрица размера `N` на `M` (`1\ ≤\ N\ ≤\ 50`, `1\ ≤\ M\ ≤\ 50`), элементы
матрицы – целые числа от 0 до 65535.
Ненулевые элементы матрицы – пиксели, задающие облако точек человека.
Требуется разделить облако точек человека не более
чем `K` (`1\ ≤\ K\ ≤\ 20`) вертикальными плоскостями таким образом,
чтобы сумма расстояний от каждой точки до ближайшей плоскости была
минимальной. В случае, если существует несколько оптимальных разделений,
необходимо выбрать то, которое содержит наименьшее количество
плоскостей. Если существует несколько вариантов с минимальным
количеством плоскостей, можно вывести любой из них.
Формат ввода
В первой строке ввода заданы числа `N`, `M` и `K`. Каждая из следующих `N` строк
содержит `M` целых чисел, задающих элементы матрицы.
Гарантируется, что матрица содержит хотя бы один ненулевой элемент.
Формат вывода
В первой строке вывести одно вещественное число – минимальное значение суммы
расстояний с точностью не менее `10^{-6}`.
Во второй строке вывести целое число `q` (`1\ ≤\ q\ ≤\ K`) – количество вертикальных плоскостей, входящих в оптимальное разбиение.
В третьей строке вывести `q` чисел через пробел – глубины разделяющих плоскостей в оптимальном разбиении с 9 десятичными знаками после точки.
Пример ввода
28 18 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 4 3 3 2 3 4 0 0 0 0 0 0 0 0 0 0 4 4 3 3 2 2 3 3 4 4 0 0 0 0 0 0 0 4 2 2 2 2 2 2 2 2 2 2 4 0 0 0 0 0 2 2 2 2 1 2 2 2 2 2 2 2 2 2 0 0 0 0 2 2 0 0 1 2 2 1 1 1 0 0 0 2 0 0 0 0 2 2 0 0 1 1 1 1 1 1 0 0 2 2 0 0 0 0 0 2 0 0 1 1 1 1 1 1 0 0 2 2 0 0 0 0 0 1 0 0 1 1 1 1 1 1 0 0 2 0 0 0 0 0 0 0 1 1 1 1 3 3 1 1 0 2 2 0 0 0 0 0 0 0 0 0 1 3 3 3 3 1 0 1 2 0 0 0 0 0 0 0 0 0 3 3 3 3 3 3 0 1 0 0 0 0 0 0 0 0 0 0 3 3 3 3 3 3 3 0 0 0 0 0 0 0 0 0 0 0 3 3 3 0 3 3 3 0 0 0 0 0 0 0 0 0 0 3 3 3 3 0 3 3 3 0 0 0 0 0 0 0 0 0 0 3 4 3 0 0 3 4 4 0 0 0 0 0 0 0 0 0 0 4 4 4 0 0 4 4 4 0 0 0 0 0 0 0 0 0 0 4 4 4 0 0 0 4 4 4 0 0 0 0 0 0 0 0 0 4 4 0 0 0 0 4 4 4 0 0 0 0 0 0 0 0 0 4 4 0 0 0 0 4 4 4 0 0 0 0 0 0 0 0 4 4 4 0 0 0 0 0 4 4 0 0 0 0 0 0 0 0 4 4 0 0 0 0 0 0 0 4 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Пример вывода
84.000000 2 1.500000000 3.500000000
