Данная задача является модификацией классической задачи о поиске двух ближайших точек среди $$$n$$$ точек заданных на плоскости.

У классического варианта задачи есть множество решений. Одно из самых популярных решений основано на принципе разделяй и властвуй и работает за $$$\mathcal{O}(n \log n)$$$. Еще есть рандомизированное решение с ожидаемым временем работы $$$\mathcal{O}(n)$$$. Эти решения уже стали классикой и их можно найти на различных ресурсах по запросу «Задача о паре ближайших точек».

Решения классической задачи работают и в данной модификации. Нужно только следить за тем, чтобы две точки, расстояние между которыми мы рассматриваем в качестве кандидата на ответ, были из разных множеств.

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