Le problème:

Étant donné un ensemble de points non vide dans le plan cartésien, trouvez le plus petit cercle qui les entoure tous ( lien Wikipedia ).

Ce problème est trivial si le nombre de points est de trois ou moins (s'il y a un point, le cercle a un rayon de zéro; s'il y a deux points, le segment de ligne qui rejoint les points est le diamètre du cercle; s'il y a trois points (non colinéaires), il est possible d'obtenir l'équation d'un cercle qui les touche tous s'ils forment un triangle non obtus, ou un cercle qui ne touche que deux points et entoure le troisième si le triangle est obtus). Donc, pour relever ce défi, le nombre de points devrait être supérieur à trois.

Le défi:

• Entrée: une liste de 4 points non colinéaires ou plus. Les points doivent avoir des coordonnées X et Y; les coordonnées peuvent être des flottants. Pour faciliter le défi, deux points ne doivent pas partager la même coordonnée X.
  Par exemple:[(0,0), (2,1), (5,3), (-1,-1)]
• Sortie: Un tuple de valeurs(h,k,r) tel que est l'équation du plus petit cercle qui entoure tous les points.$(x-h)^2 + (y-k)^2 = r^2$

Règles:

• Vous pouvez choisir la méthode de saisie qui convient à votre programme.
• La sortie doit être imprimée STDOUTou retournée par une fonction.
• Les langues «normales», à usage général, sont préférées, mais tout esolang est acceptable.
• Vous pouvez supposer que les points ne sont pas colinéaires.
• Il s'agit de code-golf, donc le plus petit programme en octets gagne. Le gagnant sera sélectionné une semaine après la publication du défi.
  • Veuillez inclure la langue que vous avez utilisée et la longueur en octets comme en-tête dans la première ligne de votre réponse: # Language: n bytes

Cas de test:

• 1:
  • Contribution: [(-8,0), (3,1), (-6.2,-8), (3,9.5)]
  • Sortie: [-1.6, 0.75, 9.89]
• 2:
  • Contribution: [(7.1,-6.9), (-7,-9), (5,10), (-9.5,-8)]
  • Sortie: [-1.73, 0.58, 11.58]
• 3:
  • Contribution: [(0,0), (1,2), (3,-4), (4,-5), (10,-10)]
  • Sortie: [5.5, -4, 7.5]
• 4:
  • Contribution: [(6,6), (-6,7), (-7,-6), (6,-8)]
  • Sortie: [0, -0.5, 9.60]

Bon golf !!!

Défi associé:

• Aire d'une coque convexe 2D

Wolfram Language (Mathematica) , 28 27 octets

#~BoundingRegion~"MinDisk"&

Essayez-le en ligne!

Les fonctions intégrées sont pratiques ici. La sortie est un objet disque avec le centre et le rayon. Comme d'autres, j'ai trouvé que les 2e et 3e cas de test étaient différents de la question.

Merci à @lirtosiast d'avoir enregistré un octet!

Si une liste est requise en sortie, cela peut être fait en 35 octets (au prix de 8 octets supplémentaires) . Merci à @Roman de l'avoir signalé.

JavaScript (ES6),  298 ... 243  242 octets

Renvoie un tableau [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

Essayez-le en ligne!

ou voir une version formatée

Comment?

Méthode

Pour chaque paire de points $(A,B)$ , on génère le cercle $(X,Y,r)$ dont le diamètre est $AB$ .

Pour chaque triple de points distincts $(A,B,C)$ , on génère le cercle $(X,Y,r)$ qui circonscrit du triangle $ABC$ .

$(x,y)$

Et nous retournons finalement le plus petit cercle valide.

la mise en oeuvre

$(X,Y)$$d\neq0$$q={C_x}^2+{C_y}^2$

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.

Gelée , 100 98 octets

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

Essayez-le en ligne!

Contrairement à ma réponse en langue Wolfram , Jelly a besoin de beaucoup de code pour y parvenir (sauf si je manque quelque chose!). Ce programme complet prend la liste des points comme argument et renvoie le centre et le rayon du plus petit cercle englobant. Il génère des cercles pour tous les ensembles de trois points et des diamètres pour tous les ensembles de deux points, vérifie tous les points, puis sélectionne celui ayant le plus petit rayon.

Le code du bit make_circumcircle a été inspiré par le code de ce site , à son tour inspiré par Wikipedia.

APL (NARS), 348 caractères, 696 octets

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⍵}

Il s'agit d'une 'implémentation' de formules dans la solution Arnauld ... Résultats et commentaires:

  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: trouve la combinaison d'alpha ojets dans l'ensemble oméga

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

((X, Y), r) représentent désormais une circonférence de rayon r et de centre dans (XY).

c: trouve si le point dans ⍺ est à l'intérieur de la circonférence ((XY) r) dans ⍵ (résultat <= 0) ot il est externe (résultat> 0) Dans le cas de la circonférence entrée dans ⍵ c'est ⍬ comme entrée, il renverrait 1 (hors circonférence) chaque entrée possible dans ⍺.

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

p: si ⍵ est un tableau de ((XY) r); pour chacun des ((XY) r) dans ⍵ écrit 1 si tous les points du tableau ⍺ sont internes à ((XY) r) sinon écrit 0 NB Voici quelque chose qui ne va pas parce que je devais arrondir à epsilon = 1e¯ 13. en d'autres termes dans des cas limites de points dans l'avion (et probablement construits exprès) ce n'est pas une solution 100% assurée

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

s2: à partir de 2 points en ⍵, il renvoie la circonférence au format ((XY) r) qui a un diamètre dans ces 2 points

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

s3: à partir de 3 points, il retourne la circonférence au format ((XY) r) passant par ces trois points S'il y a des problèmes (par exemple les points sont alignés), il échouera et retournera ⍬.

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

notons que -. × trouve le déterminant d'une matrice nxn et

  ⎕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: à partir de n points dans ⍵, il trouve les circonférences de type de celles trouvées par s2 ou celles de type s3 qui contiennent tous les n points.

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

s1: à partir de l'ensemble trouvé à partir du s ci-dessus calcule ceux qui ont un rayon minimum et renvoie le premier qui a un rayon minimum. Les trois nombres sous forme de tableaux (les première et deuxième coordonnées sont les coordonnées du centre, tandis que le troisième est le rayon de la circonférence trouvée).

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!