Problem:

Biorąc pod uwagę niepusty zestaw punktów na płaszczyźnie kartezjańskiej, znajdź najmniejsze koło, które je ogarnia ( link z Wikipedii ).

Ten problem jest trywialny, jeśli liczba punktów wynosi trzy lub mniej (jeśli jest jeden punkt, okrąg ma promień zero; jeśli są dwa punkty, odcinek linii łączący punkty jest średnicą koła; jeśli istnieją trzy (nieliniowe) punkty, możliwe jest uzyskanie równania koła, które dotyka ich wszystkich, jeśli tworzą trójkąt nie rozwarty lub koło, które dotyka tylko dwóch punktów i otacza trzeci, jeśli trójkąt jest tępy). Tak więc, ze względu na to wyzwanie, liczba punktów powinna być większa niż trzy.

Wyzwanie:

• Dane wejściowe: lista 4 lub więcej punktów innych niż kolinearne. Punkty powinny mieć współrzędne X i Y; współrzędne mogą być zmiennoprzecinkowe. Aby ułatwić wyzwanie, żadne dwa punkty nie powinny mieć tej samej współrzędnej X.
  Na przykład:[(0,0), (2,1), (5,3), (-1,-1)]
• Wyjście: krotka wartości, (h,k,r)taka, że $(x-h)^2 + (y-k)^2 = r^2$ jest równaniem najmniejszego okręgu, który obejmuje wszystkie punkty.

Zasady:

• Możesz wybrać metodę wprowadzania odpowiednią dla twojego programu.
• Dane wyjściowe powinny zostać wydrukowane STDOUTlub zwrócone przez funkcję.
• Preferowane są języki „zwykłe” ogólnego przeznaczenia, ale akceptowany jest każdy esolang.
• Możesz założyć, że punkty nie są współliniowe.
• To jest golf golfowy, więc wygrywa najmniejszy program w bajtach. Zwycięzca zostanie wybrany tydzień po opublikowaniu wyzwania.
  • Jako nagłówek w pierwszym wierszu odpowiedzi podaj użyty język i długość w bajtach: # Language: n bytes

Przypadki testowe:

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

Miłej gry w golfa !!!

Powiązane wyzwanie:

• Obszar wypukłego kadłuba 2D

Wolfram Language (Mathematica) , 28 27 bajtów

#~BoundingRegion~"MinDisk"&

Wypróbuj online!

Przydają się tutaj wbudowane. Dane wyjściowe to obiekt dyskowy o środku i promieniu. Podobnie jak inne, stwierdziłem, że 2. i 3. przypadek testowy różnią się od pytania.

Dzięki @lirtosiast za uratowanie bajtu!

Jeśli jako dane wyjściowe wymagana jest lista, można to zrobić w 35 bajtach (kosztem dodatkowych 8 bajtów) . Dzięki @Roman za zwrócenie na to uwagi.

JavaScript (ES6),  298 ... 243  242 bajtów

Zwraca tablicę [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

Wypróbuj online!

lub zobacz sformatowaną wersję

W jaki sposób?

metoda

Dla każdej pary punktów generujemy okrąg którego średnica wynosi .$(A,B)$$(X,Y,r)$$AB$

Dla każdego potrójnego punktu generujemy okrąg który otacza trójkąt .$(A,B,C)$$(X,Y,r)$$ABC$

Dla każdego wygenerowanego okręgu sprawdzamy, czy każdy punkt jest w nim zawarty:$(x,y)$

I w końcu zwracamy najmniejsze prawidłowe koło.

Realizacja

W kodzie JS wzór na obliczenie dla ograniczonego okręgu trójkąta jest nieco uproszczony. Zakładając , definiujemy , co prowadzi do:$(X,Y)$$d\neq0$$q={C_x}^2+{C_y}^2$

W ten sposób funkcja pomocnicza wymaga tylko dwóch parametrów do obliczenia każdej współrzędnej:$F$$(j,k)$

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

Trzeci parametr stosowany w (to jej rzeczywisty argumentu ) stosuje się do obliczenia , gdy , co oznacza, że trójkąt jest zdegenerowany i spróbować zamiast używać średnicę.$F$$s$$(X,Y)$$d=0$

R , 59 bajtów

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

Wypróbuj online!

Pobiera dane wejściowe jako wektor złożonych współrzędnych. Modjest odległością (modułem) w płaszczyźnie zespolonej i nlmjest funkcją optymalizacyjną: znajduje pozycję środka (wyjście as estimate), która minimalizuje maksymalną odległość do punktów wejściowych i podaje odpowiednią odległość (wyjście as minimum), tj. promień . Dokładne do 3-6 cyfr; stopka TIO zaokrągla wynik do 2 cyfr.

nlmprzyjmuje na wejściu wektor numeryczny: y%*%c(1,1i)firma przekształca go w kompleks.

Galaretka , 100 98 bajtów

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

Wypróbuj online!

W przeciwieństwie do mojej odpowiedzi w języku Wolfram , Jelly potrzebuje sporo kodu, aby to osiągnąć (chyba że czegoś mi brakuje!). Ten pełny program przyjmuje listę punktów jako argument i zwraca środek i promień najmniejszego otaczającego okręgu. Generuje on okręgi dla wszystkich zestawów trzech punktów i średnice dla wszystkich zestawów dwóch punktów, czeki, które obejmują wszystkie punkty, a następnie wybiera ten o najmniejszym promieniu.

Kod bitu make_circumcircle został zainspirowany kodem na tej stronie , z kolei zainspirowanym Wikipedią.

APL (NARS), 348 znaków, 696 bajtów

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

Jest to jedna „implementacja” formuł w rozwiązaniu Arnauld ... Wyniki i komentarze:

  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: znajduje kombinację ojetów alfa w zestawie omega

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

((X, Y), r) od teraz reprezentują jedną obwódkę o promieniu ri środku w (XY).

c: sprawdza, czy punkt w ⍺ znajduje się wewnątrz obwodu ((XY) r) w ⍵ (wynik <= 0) ot jest zewnętrzny (wynik> 0) W przypadku wprowadzenia obwodu w ⍵ jest to input jako wejście, to zwróci 1 (poza obwodem) każde możliwe wejście w ⍺.

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

p: jeśli ⍵ jest tablicą ((XY) r); dla każdego z ((XY) r) w ⍵ zapisuje 1, jeśli wszystkie punkty w tablicy ⍺ są wewnętrzne dla ((XY) r) w przeciwnym razie zapisuje 0 NB Oto coś, co nie idzie, ponieważ musiałem zaokrąglić do epsilon = 1e¯ 13 innymi słowy w ograniczonych przypadkach punktów w samolocie (i prawdopodobnie zbudowanych specjalnie) cel nie jest w 100% ubezpieczony

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

s2: od 2-punktowego w ⍵ zwraca obwód w formacie ((XY) r), który ma średnicę w tych 2 punktach

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

s3: z 3 punktów zwraca obwód w formacie ((XY) r) przechodzący przez te trzy punkty Jeśli wystąpią problemy (na przykład punkty są wyrównane), to się nie powiedzie i zwróci ⍬.

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

zauważ, że -. × znajdź wyznacznik macierzy nxn i

  ⎕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: z n punktów na ⍵, wyszukuje obwody typu znalezione przez s2 lub te typu s3, które zawierają wszystkie n punktów.

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

s1: z zestawu znalezionego z powyższego s oblicza te, które mają minimalny promień i zwraca pierwszy, który ma minimalny promień. Trzy liczby jako tablice (pierwsza i druga współrzędna są współrzędnymi środka, a trzecia to promień znalezionego obwodu).

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

Python 2 (PyPy) , 244 242 bajtów

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]

Wypróbuj online!

Wykorzystuje to algorytm O (n ^ 4) brute-force, iterujący po każdej parze i trójkącie punktów, obliczający środek i utrzymujący środek, który potrzebuje najmniejszego promienia, aby objąć wszystkie punkty. Oblicza obwód 3 punktów poprzez znalezienie przecięcia dwóch prostopadłych dwusiecznych (lub, jeśli dwa punkty są równe, wykorzystuje punkt środkowy z trzecim).

Python 212 190 bajtów

To rozwiązanie jest nieprawidłowe i muszę teraz działać, więc nie mam czasu, aby to naprawić.

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

Wypróbuj online!

Zorientowałem się, które dwa punkty są najdalej, a następnie wygenerowałem równanie dla koła na podstawie tych punktów!

Wiem, że nie jest to najkrótszy w Pythonie, ale to najlepsze, co mogłem zrobić! To także moja pierwsza próba zrobienia jednego z nich, więc proszę zrozumcie!