Роботы и обработка изображений. Практика

Совсем недавно я публиковал маленький обзор подходов к распознаванию образов.

Сейчас - хочу продолжить, на этот раз не теорией, а самой что ни на есть практикой. Всем известно, что на олимпиадах очень часто дают очень интересные задачи. Которые, на самом деле, при наличии доли сообразительности, может решить кто угодно - без всяких, причем, теоретических знаний. Предлагаю господам читателям размять косточки на нижеследующей олимпиадной задаче:

Распознавание подписей

По условиям олимпиады, на задачу отводится 160 мин. Олимпиада называется "KPI-OPEN 2007". Итак, условия:

Банку нужна программа, которая позволяет распознавать подписи клиентов на чеках. После сканирования и предварительной обработки каждая подпись представляет из себя ломаную линию, для которой известна начальная точка. Распознавание подписей производится на основе их сравнения с образцами.

О том, насколько ломаные (образец и подпись) соответствуют друг другу, можно судить по соответствию длин сегментов подписи, и углов между соответствующими сегментами подписи.

Если количество сегментов в образце и подписи не совпадают, то считают, что длины и углы для недостающих сегментов равны нулю.

Входной файл

Входной файл input.txt в первой строке содержит целое десятичное число C, 0 <= C <= 50, которое определяет количество образцов подписей. Далее следует C*2 строк, которые описывают образцы подписей.

Первая строка содержит имя клиента (не более 255 строчных букв английского алфавита). Вторая строка описывает подпись (ломаную), и содержит пары (не более 100) целых чисел от 0 до 32000 включительно, разделитель между парами - пробел. Числа в парах разделены пробелом, первое число - координата X, второе - координата Y для каждой из точек ломаной. Первая пара определяет начальную точку.

Далее во входном файле следует целое десятичное число P (от 0 до 50), которое содержит число распознаваемых подписей. P строк подписей описываются также, как в образце.

Последняя строка не заканчивается символом перевода каретки.

Выходной файл

Выходной файл output.txt первой строкой соответствует число P, равное числу из входного файла. Затем следует P строк, в каждой из которых - имя клиента, которому принадлежит распознанная подпись. Порядок строк соответствует порядку строк с распознаваемыми подписями из входного файла.

Пример (щелкните на изображении для увеличения):

Автор задачи: Болдак А.А.