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

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

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

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