Отсев соответствий по отношению расстояний

Задание

Реализуйте функцию filter_matches(candidates, ratio). Она получает кандидатов в пары для каждой точки первого кадра и возвращает только те пары, которые прошли проверку отношением.

candidates — список по числу точек первого кадра. Под номером i лежит список кандидатов для этой точки: пары (индекс точки второго кадра, расстояние между дескрипторами). Порядок кандидатов внутри списка произвольный — отсортированными они не приходят.

Правила отбора такие же, как на прогоне урока:

• у точки берутся два наименьших расстояния — до ближайшего кандидата и до следующего за ним;
• пара проходит, если расстояние до ближайшего строго меньше, чем ratio, умноженный на расстояние до второго;
• если кандидат всего один, сравнивать не с чем — такая точка пары не даёт;
• если кандидатов нет вовсе, точка пропускается.

Ответ — список пар (индекс точки первого кадра, индекс её ближайшего кандидата) по возрастанию первого индекса. Значение ratio лежит в пределах от нуля до единицы.

Пример

candidates = [
    [(4, 173.0), (7, 17.0)],
    [(2, 163.0), (9, 163.0)],
    [(5, 40.0)],
]
filter_matches(candidates, 0.75)
# [(0, 7)]

У первой точки ближайший кандидат вдесятеро ближе второго — пара проходит, и в ответ идёт индекс этого кандидата, а не его место в списке. У второй оба кандидата одинаково далеки, отношение равно единице. У третьей всего один кандидат.

Примечание

Вход уже разобран и приходит аргументами: список списков кортежей и число с плавающей точкой. Индексы — целые, расстояния — числа с плавающей точкой. Менять входные списки нельзя, в том числе сортировать их на месте.

Деления в решении можно избежать вовсе: сравнение с умножением на ratio даёт тот же ответ и не падает на нулевых расстояниях. Вызывать функцию вручную не нужно, проверка запускает её сама.

Что проверяется

Код проверок скрыт, так что вот полный список того, что в них разбирается:

• формат ответа: список кортежей из двух целых, первые индексы идут по возрастанию;
• входные списки после вызова не изменились и не пересортированы;
• пример из условия;
• кандидаты приходят не по возрастанию расстояния;
• у точки больше двух кандидатов;
• отношение ровно на пороге;
• два одинаковых наименьших расстояния;
• нулевые расстояния у обоих ближайших кандидатов;
• нулевое расстояние до ближайшего при ненулевом до второго;
• у точки один кандидат и у точки ни одного;
• ни одна точка не проходит отбор;
• пустой вход;
• ratio равен единице.