Это вопрос, который мне задавали на собеседовании некоторое время назад. И я до сих пор не могу найти разумного ответа.
Вопрос:
Вам дан набор точек (x, y). Найдите 2 самые отдаленные точки. Отдаленные друг от друга.
Например, для точек: (0,0), (1,1), (-8, 5) - наиболее удаленными являются: (1,1) и (-8,5), потому что расстояние между ними больше от (0,0) - (1,1) и (0,0) - (- 8,5).
Очевидный подход - вычислить все расстояния между всеми точками и найти максимум. Проблема в том, что это O (n ^ 2), что делает его слишком дорогим для больших наборов данных.
Существует подход с первыми точками слежения, которые находятся на границе, а затем вычисление расстояний для них, при условии, что на границе будет меньше точек, чем "внутри", но это все еще дорого, и в худшем случае потерпит неудачу сценарий.
Пытался искать в Интернете, но не нашел никакого разумного ответа - хотя это может быть просто отсутствие у меня навыков поиска.