Очевидно, что первая конечная точка должна быть на границе B. Если мы найдем самую дальнюю точку A для каждой точки границы B, у нас будет решение немедленно.Предположим, что x лежит на или внутри A, а y лежит на границе B, и они являются самой дальней парой.На данный момент мы можем сообщить (x,x+epsilon,y) как наше решение.Это означает, что если вы начинаете с «y» и двигаетесь в направлении «xy», вы можете получить самую дальнюю точку от «y».Таким образом, «х» также должен лежать на границе, конечно же, на границе B. Таким образом, ваш вопрос был сокращен, чтобы найти самую дальнюю пару, одну точку на границе A, а другую на B. В остальном вы можете сделатьбинарный поиск на каждом ребре A и B, чтобы найти то, что мы хотим.Требуется O (n ^ 2 log ^ 2 n).Конечно, вы можете запустить лучший алгоритм для последнего шага, чтобы получить лучшее время выполнения.