O problema:

Dado um conjunto não vazio de pontos no plano cartesiano, encontre o menor círculo que os inclua todos ( link da Wikipedia ).

Esse problema é trivial se o número de pontos for três ou menos (se houver um ponto, o círculo terá um raio de zero; se houver dois pontos, o segmento de linha que une os pontos será o diâmetro do círculo; se houver três pontos (não colineares), é possível obter a equação de um círculo que toca todos eles se formarem um triângulo não obtuso, ou um círculo que toca apenas dois pontos e encerra o terceiro se o triângulo for obtuso). Portanto, para o desafio deste desafio, o número de pontos deve ser maior que três.

O desafio:

• Entrada: uma lista de 4 ou mais pontos não colineares. Os pontos devem ter coordenadas X e Y; coordenadas podem ser flutuantes. Para facilitar o desafio, dois pontos não devem compartilhar a mesma coordenada X.
  Por exemplo:[(0,0), (2,1), (5,3), (-1,-1)]
• Saída: uma tupla de valores, (h,k,r)tais que é a equação do menor círculo que envolve todos os pontos.$(x-h)^2 + (y-k)^2 = r^2$

Regras:

• Você pode escolher qualquer método de entrada adequado ao seu programa.
• A saída deve ser impressa STDOUTou retornada por uma função.
• Os idiomas "normais", de uso geral, são preferidos, mas qualquer esolang é aceitável.
• Você pode assumir que os pontos não são colineares.
• Isso é código-golfe, então o menor programa em bytes vence. O vencedor será selecionado uma semana após o lançamento do desafio.
  • Inclua o idioma que você usou e o comprimento em bytes como cabeçalho na primeira linha da sua resposta: # Language: n bytes

Casos de teste:

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

Feliz golfe !!!

Desafio relacionado:

• Área de um casco 2D convexo

Wolfram Language (Mathematica) , 28 27 bytes

#~BoundingRegion~"MinDisk"&

Experimente online!

Os built-ins são úteis aqui. Saída é um objeto de disco com o centro e o raio. Como outros, eu achei o segundo e o terceiro casos de teste diferentes da questão.

Agradecemos a @lirtosiast por salvar um byte!

Se uma lista for necessária como saída, isso poderá ser feito em 35 bytes (ao custo de 8 bytes adicionais) . Agradecemos a @Roman por apontar isso.

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

Retorna uma matriz [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

Experimente online!

ou veja uma versão formatada

Quão?

Método

Para cada par de pontos $(A,B)$ , que gera o círculo $(X,Y,r)$ , cujo diâmetro é $AB$ .

Para cada triplo de pontos distintos $(A,B,C)$ , que gera o círculo $(X,Y,r)$ que circunscreve o triângulo $ABC$ .

$(x,y)$

E, finalmente, retornamos o menor círculo válido.

Implementação

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

$F$$(j,k)$

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

$F$$s$$(X,Y)$$d=0$

R , 59 bytes

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

Experimente online!

Recebe entrada como um vetor de coordenadas complexas. Modé a distância (módulo) no plano complexo e nlmé uma função de otimização: encontra a posição do centro (saída como estimate) que minimiza a distância máxima aos pontos de entrada e fornece a distância correspondente (saída como minimum), ou seja, o raio . Preciso para 3-6 dígitos; o rodapé do TIO arredonda a saída para 2 dígitos.

nlmrecebe um vetor numérico como entrada: a y%*%c(1,1i)empresa o converte em um complexo.

Geléia , 100 98 bytes

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

Experimente online!

Em contraste com a minha resposta na linguagem Wolfram , o Jelly precisa de muito código para conseguir isso (a menos que esteja perdendo alguma coisa!). Este programa completo pega a lista de pontos como argumento e retorna o centro e o raio do menor círculo fechado. Ele gera circuitos para todos os conjuntos de três pontos e diâmetros para todos os conjuntos de dois pontos, verificações que incluem todos os pontos e, em seguida, seleciona aquele com o menor raio.

O código do bit make_circumcircle foi inspirado no código deste site , por sua vez, inspirado na Wikipedia.

APL (NARS), 348 caracteres, 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⍵}

Esta é uma 'implementação' de fórmulas na solução Arnauld ... Resultados e comentários:

  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: encontra a combinação de alfa ojets no conjunto ômega

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

((X, Y), r) a partir de agora representam uma circonferência do raio r e centro em (XY).

c: descobre se o ponto em ⍺ está dentro da circunferência ((XY) r) em ⍵ (resultado <= 0) ou é externo (resultado> 0) No caso da entrada da circunferência em ⍵ é ⍬ como entrada, é retornaria 1 (fora da circunferência) cada entrada possível em ⍺.

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

p: se ⍵ é uma matriz de ((XY) r); para cada um dos ((XY) r) em ⍵ escreve 1 se todos os pontos da matriz ⍺ são internos para ((XY) r) escreve de outra forma 0 NB Aqui está algo que não vale porque eu tive que arredondar para epsilon = 1e¯ 13) em outras palavras, em casos limitados de pontos no avião (e provavelmente criados de propósito), não é 100% a solução segurada

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

s2: de 2 pontos em ⍵, retorna a circunferência no formato ((XY) r) que possui diâmetro nesses 2 pontos

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

s3: a partir de 3 pontos, retorna a circunferência no formato ((XY) r) passando por esses três pontos. Se houver problemas (por exemplo, os pontos estão alinhados), ela falhará e retornará ⍬.

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 que -. × encontra o determinante de uma matriz nxn e

  ⎕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: de n pontos em ⍵, encontra as circunferências de tipo daquelas encontradas por s2 ou as do tipo s3 que contêm todos os n pontos.

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

s1: do conjunto encontrado dos s acima calcula aqueles que possuem raio mínimo e retorna o primeiro que possui raio mínimo. Os três números como matrizes (a primeira e a segunda coordenadas são as coordenadas do centro, enquanto o terceiro é o raio da circunferência encontrada).

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]

Experimente online!

Isso usa o algoritmo de força bruta O (n ^ 4), percorrendo cada par e triângulo de pontos, calculando o centro e mantendo o centro que precisa do menor raio para incluir todos os pontos. Ele calcula o perímetro de 3 pontos, encontrando a interseção de dois bissetores perpendiculares (ou, se dois pontos são iguais, ele usa o ponto médio com o terceiro).

Python 212 190 bytes

Esta solução está incorreta e tenho que trabalhar agora para não ter tempo para corrigi-la.

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))

Experimente online!

Eu descobri quais são os dois pontos mais distantes e, em seguida, gerei uma equação para um círculo baseado nesses pontos!

Eu sei que isso não é o mais curto em python, mas é o melhor que eu poderia fazer! Além disso, esta é a minha primeira tentativa de fazer uma delas, então, por favor, seja compreensivo!