Проблема:

Учитывая непустое множество точек в декартовой плоскости, найдите наименьший круг, который охватывает их все ( ссылка на Википедию ).

Эта проблема тривиальна, если число точек равно трем или меньше (если есть одна точка, радиус окружности равен нулю; если имеется две точки, то отрезок линии, соединяющий точки, является диаметром круга; если есть В трех (не коллинеарных) точках можно получить уравнение окружности, которая касается их всех, если они образуют не тупой треугольник, или окружность, которая касается только двух точек и окружает третью, если треугольник тупой). Итак, ради этого испытания количество очков должно быть больше трех.

Соревнование:

• Ввод: список из 4 или более неколинейных точек. Точки должны иметь координаты X и Y; координаты могут быть плавающими. Чтобы облегчить задачу, никакие две точки не должны иметь одинаковую координату X.
  Например:[(0,0), (2,1), (5,3), (-1,-1)]
• Вывод: кортеж значений, (h,k,r)такой что $(x-h)^2 + (y-k)^2 = r^2$ - это уравнение наименьшего круга, охватывающего все точки.

Правила:

• Вы можете выбрать любой метод ввода, подходящий для вашей программы.
• Вывод должен быть напечатан STDOUTили возвращен функцией.
• «Обычные» языки общего назначения предпочтительны, но приемлем любой язык.
• Можно предположить, что точки не являются коллинеарными.
• Это код-гольф, поэтому выигрывает самая маленькая программа в байтах. Победитель будет выбран через неделю после объявления конкурса.
  • Пожалуйста, укажите язык, который вы использовали, и длину в байтах в качестве заголовка в первой строке вашего ответа: # Language: n bytes

Тестовые случаи:

• 1:
  • Входные данные: [(-8,0), (3,1), (-6.2,-8), (3,9.5)]
  • Выход: [-1.6, 0.75, 9.89]
• 2:
  • Входные данные: [(7.1,-6.9), (-7,-9), (5,10), (-9.5,-8)]
  • Выход: [-1.73, 0.58, 11.58]
• 3:
  • Входные данные: [(0,0), (1,2), (3,-4), (4,-5), (10,-10)]
  • Выход: [5.5, -4, 7.5]
• 4:
  • Входные данные: [(6,6), (-6,7), (-7,-6), (6,-8)]
  • Выход: [0, -0.5, 9.60]

Удачного игры в гольф !!!

Связанная проблема:

• Площадь двумерного выпуклого корпуса

Wolfram Language (Mathematica) , 28 27 байтов

#~BoundingRegion~"MinDisk"&

Попробуйте онлайн!

Встроенные модули здесь удобны. Выход - это дисковый объект с центром и радиусом. Как и другие, я обнаружил, что 2-й и 3-й тестовые случаи отличаются от вопроса.

Спасибо @lirtosiast за сохранение байта!

Если список требуется в качестве выходных данных, это может быть сделано в 35 байтах (за счет дополнительных 8 байтов) . Спасибо @Roman за указание на это.

JavaScript (ES6),  298 ... 243  242 байта

Возвращает массив [x, y, r].

p=>p.map(m=([c,C])=>p.map(([b,B])=>p.map(([a,A])=>p.some(([x,y])=>H(x-X,y-Y)>r,F=s=>Y=(d?((a*a+A*A-q)*j+(b*b+B*B-q)*k)/d:s)/2,d=c*(A-B)+a*(j=B-C)+b*(k=C-A),r=H(a-F(a+b),A-F(A+B,X=Y,j=c-b,k=a-c)))|r>m?0:o=[X,Y,m=r]),q=c*c+C*C),H=Math.hypot)&&o

Попробуйте онлайн!

или посмотрите отформатированную версию

Как?

метод

Для каждой пары точек $(A,B)$ , мы создаем круг $(X,Y,r)$ , диаметр которого Б .$AB$

Для каждой тройки различных точек $(A,B,C)$ , мы создаем круг $(X,Y,r)$ , который огибает треугольник B C .$ABC$

For each generated circle, we test whether each point $(x,y)$ is enclosed within it:

And we eventually return the smallest valid circle.

Implementation

In the JS code, the formula to compute $(X,Y)$ for the triangle's circumscribed circle is slightly simplified. Assuming $d\neq0$, we define $q={C_x}^2+{C_y}^2$, leading to:

This way, the helper function $F$ requires only two parameters $(j,k)$ to compute each coordinate:

• $(B_y-C_y,\;C_y-A_y)$ for $X$
• $(C_x-B_x,\;A_x-C_x)$ for $Y$

The third parameter used in $F$ (i.e. its actual argument $s$) is used to compute $(X,Y)$ when $d=0$, meaning that the triangle is degenerate and we have to try to use the diameter instead.

R, 59 bytes

function(x)nlm(function(y)max(Mod(x-y%*%c(1,1i))),0:1)[1:2]

Try it online!

Takes input as a vector of complex coordinates. Mod is the distance (modulus) in the complex plane and nlm is an optimization function: it finds the position of the center (output as estimate) which minimizes the maximum distance to the input points, and gives the corresponding distance (output as minimum), i.e. the radius. Accurate to 3-6 digits; the TIO footer rounds the output to 2 digits.

nlm takes a numeric vector as input: the y%*%c(1,1i) business converts it to a complex.

Jelly, 100 98 bytes

_²§½
1ịṭƊZIṚṙ€1N1¦,@ṭ@²§$µḢZḢ×Ø1œị$SḤ÷@P§
ZṀ+ṂHƲ€_@Ç+ḷʋ⁸,_²§½ʋḢ¥¥
œc3Ç€;ŒcZÆm,Hñ/$Ʋ€$ñ_ƭƒⱮṀ¥Ðḟ⁸ṚÞḢ

Try it online!

In contrast to my Wolfram language answer, Jelly needs quite a lot of code to achieve this (unless I’m missing something!). This full program takes the list of points as its argument and returns the centre and radius of the smallest enclosing circle. It generates circumcircles for all sets of three points, and diameters for all sets of two points, checks which include all of the points and then picks the one with the smallest radius.

Code for the make_circumcircle bit was inspired by code at this site, in turn inspired by Wikipedia.

APL(NARS), 348 chars, 696 bytes

f←{h←{0=k←⍺-1:,¨⍵⋄(k<0)∨k≥i←≢w←⍵:⍬⋄↑,/{w[⍵],¨k h w[(⍳i)∼⍳⍵]}¨⍳i-k}⋄1≥≡⍵:⍺h⍵⋄⍺h⊂¨⍵}
c←{⍵≡⍬:1⋄(x r)←⍵⋄(-r*2)++/2*⍨⍺-x}
p←{(b k)←⍺ ⍵⋄∧/¨1e¯13≥{{⍵{⍵c⍺}¨b}k[⍵]}¨⍳≢k}
s2←{(+/k),√+/↑2*⍨-/k←2÷⍨⍵}
s3←{0=d←2×-.×m←⊃{⍵,1}¨⍵:⍬⋄m[;1]←{+/2*⍨⍵}¨⍵⋄x←d÷⍨-.×m⋄m[;2]←{1⊃⍵}¨⍵⋄y←d÷⍨--.×m⋄(⊂x y),√+/2*⍨(x y)-1⊃⍵}
s←{v/⍨⍵p v←(s2¨2 f⍵)∪s3¨3 f⍵}
s1←{↑v/⍨sn=⌊/sn←{2⊃⍵}¨v←s⍵}

This is one 'implementation' of formulas in Arnauld solution...Results and comments:

  s1 (¯8 0)(3 1)(¯6.2 ¯8)(3 9.5)
¯1.6 0.75  9.885469134 
  s1 (7.1 ¯6.9)(¯7 ¯9)(5 10)(¯9.5 ¯8)
¯1.732305109 0.5829680042  11.57602798 
  s1 (0 0)(1 2)(3 ¯4)(4 ¯5)(10 ¯10)
5.5 ¯4  7.5 
  s1 (6 6)(¯6 7)(¯7 ¯6)(6 ¯8)
0 ¯0.5  9.604686356 
  s1 (6 6)(¯6 7)(¯7 ¯6)(6 ¯8)(0 0)(1 2)(3 ¯4)(4 ¯5)(10 ¯10)
2 ¯1.5  11.67261753 
  s1 (6 6)(¯6 7)(¯7 ¯6)(6 ¯8)(1 2)(3 ¯4)(4 ¯5)(10 ¯10)(7.1 ¯6.9)(¯7 ¯9)(5 10)(¯9.5 ¯8)
1.006578947 ¯1.623355263  12.29023186 
  s1 (1 1)(2 2)(3 3)(4 4)
2.5 2.5  2.121320344 
  ⎕fmt s3 (1 1)(2 2)(3 3)(4 4)
┌0─┐
│ 0│
└~─┘

f: finds the combination of alpha ojets in the omega set

f←{h←{0=k←⍺-1:,¨⍵⋄(k<0)∨k≥i←≢w←⍵:⍬⋄↑,/{w[⍵],¨k h w[(⍳i)∼⍳⍵]}¨⍳i-k}⋄1≥≡⍵:⍺h⍵⋄⍺h⊂¨⍵}

((X,Y), r) from now represent one circonference of radius r and center in (X Y).

c: finds if the point in ⍺ is inside the circumference ((X Y) r) in ⍵ (result <=0) ot it is external (result >0) In the case of circumference input in ⍵ it is ⍬ as input, it would return 1 (out of circumference) each possible input in ⍺.

c←{⍵≡⍬:1⋄(x r)←⍵⋄(-r*2)++/2*⍨⍺-x}

p: if ⍵ is an array of ((X Y) r); for each of the ((X Y) r) in ⍵ writes 1 if all points in the array ⍺ are internal to ((X Y) r) otherwise writes 0 NB Here's something that do not goes because I had to round to epsilon= 1e¯13. in other words in limit cases of points in the plane (and probably built on purpose) it is not 100% solution insured

p←{(b k)←⍺ ⍵⋄∧/¨1e¯13≥{{⍵{⍵c⍺}¨b}k[⍵]}¨⍳≢k}

s2: from 2-point in ⍵, it returns the circumference in the format ((X Y) r) that has diameter in those 2 points

s2←{(+/k),√+/↑2*⍨-/k←2÷⍨⍵}

s3: from 3 points it return the circumference in the format ((X Y) r) passing through those three points If there are problems (for example points are aligned), it would fail and return ⍬.

s3←{0=d←2×-.×m←⊃{⍵,1}¨⍵:⍬⋄m[;1]←{+/2*⍨⍵}¨⍵⋄x←d÷⍨-.×m⋄m[;2]←{1⊃⍵}¨⍵⋄y←d÷⍨--.×m⋄(⊂x y),√+/2*⍨(x y)-1⊃⍵}

note that -.× find the determinant of a matrix nxn and

  ⎕fmt ⊃{⍵,1}¨(¯8 0)(3 1)(¯6.2 ¯8)
┌3─────────┐     
3 ¯8    0 1│     |ax  ay 1|
│  3    1 1│   d=|bx  by 1|=ax(by-cy)-bx(ay-cy)+cx(ay-by)=ax(by-cy)+bx(cy-ay)+cx(ay-by)
│ ¯6.2 ¯8 1│     |cx  cy 1|
└~─────────┘

s: from n points in ⍵, it finds the type circumferences of those found by s2 or those of type s3 that contain all n points.

s←{v/⍨⍵p v←(s2¨2 f⍵)∪s3¨3 f⍵}

s1: from the set found from the s above calculates those that have minimum radius and returns the first one that has minimal radius. The three numbers as arrays (the first and second coordinates are the coordinates of the center, while the third is the radius of the circumference found).

s1←{↑v/⍨sn=⌊/sn←{2⊃⍵}¨v←s⍵}

Python 2 (PyPy), 244 242 bytes

P={complex(*p)for p in input()}
Z=9e999,
for p in P:
 for q in{p}^P:
	for r in{p}^P:R,S=1j*(p-q),q-r;C=S.imag and S.real/S.imag-1jor 1;c=(p+q-(S and(C*(p-r)).real/(C*R).real*R))/2;Z=min(Z,(max(abs(c-t)for t in P),c.imag,c.real))
print Z[::-1]

Try it online!

This uses the brute-force O(n^4) algorithm, iterating through each pair and triangle of points, calculating the centre, and keeping the centre that needs the smallest radius to enclose all points. It calculates the circumcentre of 3 points via finding the intersection of two perpendicular bisectors (or, if two points are equal it uses the midpoint with the third).

Python 212 190 bytes

This solution is incorrect, and I have to work now so I do not have time to fix it.

a=eval(input())
b=lambda a,b: ((a[0]-b[0])**2+(a[1]-b[1])**2)**.5
c=0
d=1
for e in a:
    for f in a:
        g=b(e,f)
        if g>c:
            c=g
            d=[e,f]
print(((d[0][0]+d[1][0])/2,(d[0][1]+d[1][1])/2,c/2))

Try it online!

I figured out which two points are furthest and then I generated an equation for a circle based off those points!

I know this isn't the shortest in python, but it's the best I could do! Also this is my first attempt at doing one of these, so please be understanding!