Классификация мультитач жестов
С появлением сенсорных экранов разработчикам программного обеспечения пришлось переосмыслить управление компьютером с помощью жестов пальцами. Одной из ключевых задач в распознавании жестов является классификация касаний в один из нескольких возможных жестов. Это может быть непросто, поскольку касания представляют собой пятна пикселей на экране, а не отдельные точки, и жесты включают движение.
Мы определяем касание как связанный набор пикселей. Два пикселя принадлежат одному касанию, если они горизонтально или вертикально смежны. Точка касания — это среднее положение всех пикселей в наборе.
Захват — это совокупность всех точек касания на изображении. Точка захвата — это среднее положение всех точек касания в захвате. Для каждой точки касания мы определяем её вектор касания как вектор от точки захвата до точки касания. Жест — это пара захватов (начальный и конечный), и оба захвата имеют одинаковое количество касаний. Соответствие между касаниями в начальном и конечном захвате выбирается так, чтобы сумма квадратов расстояний между соответствующими точками касания была минимальной.
Существует три вида жестов: панорамирование, масштабирование и вращение. С каждым видом связана определённая дистанция. Дистанция панорамирования измеряется между двумя точками захвата. Размах захвата — это среднее расстояние между каждой точкой касания и точкой захвата. Дистанция масштабирования — это разница между двумя размахами захвата. Вращение касания — это подписанный угол (в (−, ) радианах) между двумя векторами касания для соответствующих точек касания (равный нулю, если любой вектор касания имеет нулевую длину). Вращение захвата — это среднее вращение касания. Дистанция вращения — это длина дуги вращения захвата по кругу с радиусом, равным размаху захвата начального захвата.
Вам нужно классифицировать жесты в зависимости от того, является ли это панорамированием, масштабированием или вращением. Выберите тот, который имеет наибольшую связанную дистанцию.
Входные данные
Входные данные — это одна пара изображений, расположенных рядом. Оба изображения имеют размер 15×30 пикселей, и на каждой строке будет один пробел, разделяющий два изображения. Каждое изображение использует X для обозначения пикселей касания и точку (.) для обозначения отсутствия касания. Оба изображения имеют одинаковое количество касаний, от 1 до 5.
Выходные данные
Выведите количество касаний и тип жеста (панорамирование, масштабирование или вращение), а также направление жеста для масштабирования или вращения. Направление для масштабирования — вглубь, если размах захвата конечного захвата меньше, чем начального, иначе — наружу. Направление вращения — либо по часовой стрелке, либо против часовой стрелки. Все сравнения дистанций, влияющие на выходные данные, будут устойчивы к числовой погрешности 10^{−5}.