Das Problem:
Suchen Sie bei einer nicht leeren Menge von Punkten in der kartesischen Ebene den kleinsten Kreis, der sie alle einschließt ( Wikipedia-Link ).
Dieses Problem ist trivial, wenn die Anzahl der Punkte drei oder weniger beträgt (wenn es einen Punkt gibt, hat der Kreis einen Radius von Null; wenn es zwei Punkte gibt, ist das Liniensegment, das die Punkte verbindet, der Durchmesser des Kreises; wenn es solche gibt) Bei drei (nicht-kolinearen) Punkten ist es möglich, die Gleichung eines Kreises zu erhalten, der sie alle berührt, wenn sie ein nicht-stumpfes Dreieck bilden, oder eines Kreises, der nur zwei Punkte berührt und den dritten einschließt, wenn das Dreieck stumpf ist. Aus diesem Grund sollte die Anzahl der Punkte mehr als drei betragen.
Die Herausforderung:
- Eingabe: Eine Liste von 4 oder mehr nicht-kolinearen Punkten. Die Punkte sollten X- und Y-Koordinaten haben. Koordinaten können Floats sein. Um die Herausforderung zu erleichtern, sollten keine zwei Punkte dieselbe X-Koordinate haben.
Beispielsweise:[(0,0), (2,1), (5,3), (-1,-1)]
- Ausgabe: Ein Tupel von Werten,
(h,k,r)
so dass die Gleichung des kleinsten Kreises ist, der alle Punkte einschließt.
Regeln:
- Sie können die für Ihr Programm geeignete Eingabemethode auswählen.
- Die Ausgabe sollte auf
STDOUT
eine Funktion gedruckt oder von dieser zurückgegeben werden. - "Normale" Mehrzwecksprachen werden bevorzugt, es ist jedoch jede andere Sprache akzeptabel.
- Sie können davon ausgehen, dass die Punkte nicht kollinear sind.
- Das ist Code-Golf, also gewinnt das kleinste Programm in Bytes. Der Gewinner wird eine Woche nach dem Absenden der Challenge ermittelt.
- Bitte geben Sie die von Ihnen verwendete Sprache und die Länge in Bytes als Überschrift in der ersten Zeile Ihrer Antwort an:
# Language: n bytes
- Bitte geben Sie die von Ihnen verwendete Sprache und die Länge in Bytes als Überschrift in der ersten Zeile Ihrer Antwort an:
Testfälle:
- 1:
- Eingang:
[(-8,0), (3,1), (-6.2,-8), (3,9.5)]
- Ausgabe:
[-1.6, 0.75, 9.89]
- Eingang:
- 2:
- Eingang:
[(7.1,-6.9), (-7,-9), (5,10), (-9.5,-8)]
- Ausgabe:
[-1.73, 0.58, 11.58]
- Eingang:
- 3:
- Eingang:
[(0,0), (1,2), (3,-4), (4,-5), (10,-10)]
- Ausgabe:
[5.5, -4, 7.5]
- Eingang:
- 4:
- Eingang:
[(6,6), (-6,7), (-7,-6), (6,-8)]
- Ausgabe:
[0, -0.5, 9.60]
- Eingang:
Viel Spaß beim Golfen !!!
Antworten:
Wolfram Language (Mathematica) ,
2827 BytesProbieren Sie es online!
Eingebaute sind hier praktisch. Die Ausgabe ist ein Plattenobjekt mit Mittelpunkt und Radius. Wie bei anderen habe ich festgestellt, dass sich der 2. und 3. Testfall von der Frage unterscheiden.
Vielen Dank an @lirtosiast für das Speichern eines Bytes!
Wenn eine Liste als Ausgabe erforderlich ist, kann dies in 35 Bytes (auf Kosten von zusätzlichen 8 Bytes) erfolgen . Vielen Dank an @Roman für den Hinweis.
quelle
Append@@BoundingRegion[#,"MinDisk"]&
JavaScript (ES6),
298 ... 243242 ByteGibt ein Array zurück
[x, y, r]
.Probieren Sie es online!
oder sehen Sie eine formatierte Version
Wie?
Methode
Für jedes Paar von Punkten( A , B ) erzeugen wir den Kreis ( X, Y, R ) , deren Durchmesser A B .
Für jedes Tripel verschiedener Punkte(A,B,C) erzeugen wir den Kreis (X,Y,r) der das Dreieck ABC umschreibt .
Für jeden erzeugten Kreis testen wir, ob jeder Punkt( x , y) darin eingeschlossen ist:
Und wir geben schließlich den kleinsten gültigen Kreis zurück.
Implementierung
Der dritte Parameter inF s ( X, Y) d= 0
quelle
R , 59 Bytes
Probieren Sie es online!
Übernimmt die Eingabe als Vektor komplexer Koordinaten.
Mod
ist der Abstand (Modul) in der komplexen Ebene undnlm
ist eine Optimierungsfunktion: Sie ermittelt die Position des Zentrums (Ausgabe alsestimate
), die den maximalen Abstand zu den Eingabepunkten minimiert, und gibt den entsprechenden Abstand (Ausgabe als) anminimum
) an, dh den Radius . Genaue 3-6 Ziffern; Die TIO-Fußzeile rundet die Ausgabe auf zwei Ziffern.nlm
Verwendet einen numerischen Vektor als Eingabe: Dasy%*%c(1,1i)
Unternehmen wandelt ihn in einen Komplex um.quelle
Jelly ,
10098 BytesProbieren Sie es online!
Im Gegensatz zu meiner Wolfram-Antwortsprache benötigt Jelly ziemlich viel Code, um dies zu erreichen (es sei denn, ich vermisse etwas!). Dieses vollständige Programm verwendet die Liste der Punkte als Argument und gibt den Mittelpunkt und den Radius des kleinsten umschließenden Kreises zurück. Es werden für alle Sätze von drei Punkten Umkreiskreise und für alle Sätze von zwei Punkten Durchmesser generiert. Dabei werden alle Punkte überprüft und derjenige mit dem kleinsten Radius ausgewählt.
Code für das make_circumcircle-Bit wurde von Code auf dieser Site inspiriert, der wiederum von Wikipedia inspiriert wurde.
quelle
APL (NARS), 348 Zeichen, 696 Byte
Dies ist eine 'Implementierung' von Formeln in der Arnauld-Lösung ... Ergebnisse und Kommentare:
f: Findet die Kombination von Alpha-Ojets im Omega-Set
((X, Y), r) repräsentieren ab jetzt einen Kreisumfang von Radius r und Mittelpunkt in (XY).
c: Findet, ob der Punkt in ⍺ innerhalb des Umfangs ((XY) r) in ⍵ liegt (Ergebnis <= 0) oder extern ist (Ergebnis> 0). Wenn der Umfang in ⍵ eingegeben wird, ist er ⍬ als Eingabe würde 1 (außerhalb des Umfangs) für jede mögliche Eingabe in ⍺ zurückgeben.
p: wenn ⍵ ein Array von ((XY) r) ist; für jedes der ((XY) r) in ⍵ schreibe 1, wenn alle Punkte im Array ⍺ intern zu ((XY) r) sind, sonst schreibe 0 NB Hier ist etwas, das nicht geht, weil ich auf epsilon = 1e ¯ runden musste 13. in Grenzfällen von Punkten in der Ebene (und wahrscheinlich absichtlich gebaut) ist es nicht zu 100% lösungsversichert
s2: von 2-Punkt in ⍵ wird der Umfang in dem Format ((XY) r) zurückgegeben, das in diesen 2 Punkten den Durchmesser hat
s3: von 3 Punkten gibt es den Umfang in dem Format ((XY) r) zurück, das durch diese drei Punkte verläuft. Wenn es Probleme gibt (zum Beispiel Punkte sind ausgerichtet), würde es fehlschlagen und ⍬ zurückgeben.
beachte, dass -. × die Determinante einer Matrix nxn und
s: Ermittelt aus n Punkten in ⍵ die Typumfänge der von s2 gefundenen oder der vom Typ s3, die alle n Punkte enthalten.
s1: berechnet aus der Menge aus dem obigen s diejenigen mit minimalem Radius und gibt die erste mit minimalem Radius zurück. Die drei Zahlen als Arrays (die erste und die zweite Koordinate sind die Koordinaten des Zentrums, während die dritte der Radius des gefundenen Umfangs ist).
quelle
Python 2 (PyPy) ,
244242 BytesProbieren Sie es online!
Hierbei wird der Brute-Force-O (n ^ 4) -Algorithmus verwendet, der jedes Punktpaar und -dreieck durchläuft, den Mittelpunkt berechnet und den Mittelpunkt beibehält, der den kleinsten Radius benötigt, um alle Punkte einzuschließen. Der Umfang von 3 Punkten wird berechnet, indem der Schnittpunkt von zwei senkrechten Winkelhalbierenden ermittelt wird (oder wenn zwei Punkte gleich sind, wird der Mittelpunkt mit dem dritten Punkt verwendet).
quelle
P={x+y*1j for x,y in input()}
Spart auch 2 Bytes.Python
212190 BytesDiese Lösung ist falsch, und ich muss jetzt arbeiten, damit ich keine Zeit habe, sie zu beheben.
Probieren Sie es online!
Ich habe herausgefunden, welche zwei Punkte am weitesten entfernt sind, und dann eine Gleichung für einen Kreis aus diesen Punkten erstellt!
Ich weiß, dass dies nicht die kürzeste in Python ist, aber es ist das Beste, was ich tun kann! Dies ist auch mein erster Versuch, einen dieser Schritte durchzuführen. Bitte haben Sie Verständnis dafür!
quelle
if g>c:\n c=g\n d=[e,f]
zum Beispiel auf verkürzenif g>c:c=g;d=[e,f]
und so viel Leerzeichen sparen. Ich denke nicht, dass Sie d im Voraus initialisieren müssen, auch wenn Sie zwei Variablen verwenden, undE,F=e,f
in Zeile 10 werden Sieprint
viel kürzer. Ich denke, eine Lösung mitmax
und ein Listenverständnis wären sogar kürzer als zwei Schleifen, aber ich könnte mich irren. Leider ist Ihre Lösung jedoch nicht korrekt. Für die Punkte (-1,0), (0,1,41), (0,5, 0), (1,0) berechnet Ihre Lösung einen Kreis um 0 mit Radius 1. Aber der Punkt (1, 1,41) liegt nicht darin Kreis.