Нужно реализовать интересный алгоритм

Помогите пожалуйста реализовать данный алгоритм на Python 3

Алгоритм описывает нахождение минимальной окружности описывающей все заданные точки.
На вход подается некое множество точке в декартовой системе координат, а на выходе требуется найти произвольную точку, которая будет являться центром МИНИМАЛЬНОЙ окружности.



Сперва приведем алгоритм, корректность которого позднее будет доказана.

Рассмотрим метод MinDisc, который будет принимать на вход множество точек, а возвращать будет искомую охватывающую окружность. Идея метода в том, что он генерирует случайную перестановку из точек, которые поступили на вход и в получившимся порядке по одной добавляет их в текущую охватывающую окружность. Как будет доказано позднее, если на каком-то шаге алгоритма текущая точка оказалась вне текущей минимальной окружности, то утверждается, что она лежит на границе новой окружности, которая будет содержать в себе ее и все предыдущие точки. Опишем приведенный выше алгоритм псевдокодом:

MinDisc(S)
Let P - random permutation of S
Let D2 - be the smallest enclosing disc for {p1, p2}.
for i = 3 to n {
if pi ∈ Di−1 then Di = Di−1 // point is inside. nothing to do here
else Di = MinDiscWithPoint ({p1,...,pi−1}, pi) // point is lying on the boundary of minimal circle
}
return Dn
Как вы заметили, мы использовали выше метод MinDiscWithPoint - это метод, который по множеству точек и еще одной точке возвращают искомую окружность. При этом выделенная точка (которая передается в качестве второго аргумента) обязательно лежит на окружности. Эта функция очень похожа на предыдущую, поэтому приведу лишь ее псевдокод:

MinDiscWithPoint(S, q)
Let P - random permutation of S
Let D1 - be the smallest enclosing disc for {p1, q}.
for i = 2 to n {
if pi ∈ Di−1 then Di = Di−1
else Di = MinDiscWith2Points ({p1,...,pi−1}, pi, q)
}
return Dn
Как и в предыдущем случае мы использовали новый метод. MinDiscWith2Points аналогичен MinDiscWithPoint, но в нем уже передается две точки, которые будут лежать на построенной окружности. В этой функции шафлить инпут не требуется. Опишем его псевдоком:

MinDiscWith2Points(P, q1, q2)
Let D0 - be the smallest enclosing disc for {q1, q2}.
for i = 1 to n {
if pi ∈ Di−1 then Di = Di−1
else Di = сircumcircle (прим. описанная окружность) of a triangle {pi, q1, q2}
}
return Dn

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

0

Satt18, так а что ещё нужно?

0