Заметим, что если для каждой пары островов мы научимся находить минимальное расстояние, которое нужно пролететь Беззубику, чтобы попасть с одного острова на другой, то после этого нужно будет найти минимальное расстояние в графе от одной вершины до другой, где вершины — это острова. Это стандартная задача, которая решается, например, алгоритмом Дейкстры.
Находить минимальное расстояние между двумя многоугольниками можно за разную асимптотику. Минимальный по длине путь между двумя многоугольниками — это всегда отрезок, соединяющий две стороны данных многоугольников. Поэтому, можно для каждой пары многоугольников перебрать все пары сторон и сделать два вложенных тернарных поиска, получится асимптотика $$$O(k^2 \cdot P^2)$$$ для каждой пары многоугольников, где $$$P$$$ — количество итераций тернарного поиска, необходимых, чтобы достичь нужной точности ($$$P \approx 50$$$).
Далее, можно заметить, что раз никакие два многоугольника не пересекаются, не пересекаются и никакие две стороны двух разных многоугольников. Поэтому всегда найдется отрезок, соединяющий вершину одного многоугольника и сторону другого, который будет минимальным по длине путем между ними. Значит, можно избавиться от вложенного тернарного поиска. Получается асимптотика $$$O(k^2 \cdot P)$$$.
Далее, можно заметить, что для нахождения расстояния от точки до отрезка, не нужно использовать тернарный поиск, и его можно вычислить за $$$O(1)$$$, тогда асимптотика становится равна $$$O(k^2)$$$ для каждой пары многоугольников.
Наконец, полное решение использует алгоритм вычисления растояния между двумя многоугольниками с помощью суммы Минковского. Построение суммы Минковского двух многоугольников можно выполнить или за $$$O(k \cdot \log(k))$$$, или за $$$O(k)$$$. Подробнее про нахождение расстояния между двумя выпуклыми многоугольниками с помощью суммы Минковского можно почитать здесь: http://neerc.ifmo.ru/school/io/archive/20190302/geometry_doc.pdf.