A, B, C, D
Berechnen Sie bei 4 Punkten auf den 2D-Ebenen die Fläche des Schnittbereichs der Dreiecke OAB
und OCD
, wo O
sich der Mittelpunkt der Ebene befindet, die Koordinate (0, 0)
.
Algorithmen, die in konstanter zeitlicher Komplexität (in Bezug auf arithmetische Operationen) ablaufen, werden empfohlen, aber nicht erzwungen.
Regeln
- Jeder Punkt wird als zwei reelle Zahlen dargestellt und bezeichnet deren X- und Y-Koordinate.
- Wenn Ihre Programmiersprache (oder eine Bibliothek Ihrer Programmiersprache) über einen integrierten
Point
Typ oder einen entsprechenden Typ verfügt, kann optional einPoint
Objekt als Eingabe verwendet werden.
- Wenn Ihre Programmiersprache (oder eine Bibliothek Ihrer Programmiersprache) über einen integrierten
- Die Eingabe erfolgt in Formaten mit 4 Punkten, einschließlich, aber nicht beschränkt auf:
- Eine Liste von 8 Koordinaten.
- Eine Liste von 4 Punkten, jeder Punkt kann in einem beliebigen Format dargestellt werden.
- Zwei Listen mit 2 Punkten.
- etc.
- Sie können keine bestimmte Reihenfolge der Punkte annehmen (gegen den Uhrzeigersinn oder im Uhrzeigersinn)
- Sie können nicht davon ausgehen, dass der Punkt
O
als Eingabe übergeben wird. Mit anderen Worten, das Programm darf keine fremden Eingaben verwenden. - Sie können nicht davon ausgehen, dass alle Punkte unterschiedlich sind. Mit anderen Worten können die Dreiecke entartet sein. Sie müssen auch diesen Fall behandeln (siehe Testfälle unten)
- Die absolute oder relative Differenz muss geringer sein als in den folgenden Beispieltestfällen.
10-3
Gewinnkriterien
Dies ist Code-Golf , die kürzeste Antwort in Bytes zu gewinnen!
Beispiel-Testfälle
Ax Ay Bx By Cx Cy Dx Dy area
5 1 1 3 -1 0 0 -1 0
5 1 1 3 -1 0 0 0 0
5 1 1 3 0 0 0 0 0
5 1 1 3 3 4 4 -3 4.50418
5 1 1 3 1 2 2 1 1.5
5 1 1 3 -2 5 4 -2 1.74829
5 1 1 3 -2 5 5 4 2.96154
5 1 1 3 3 5 5 4 1.88462
5 1 1 3 3 5 3 1 3.92308
5 1 1 3 3 5 4 -1 5.26619
5 1 1 3 5 1 4 -1 0
5 1 1 3 5 1 1 3 7
1 3 1 3 5 1 1 3 0
1 3 1 3 1 3 1 3 0
4 8 4 -1 -2 6 -2 -3 0
1.2 3.4 -0.3 4.2 5 7.6 -1.1 2.4 2.6210759326188535
3.1 0.6 0.1 7.2 5.2 0.7 0.9 8 9.018496993987977
Hier sind die Ausgaben für die erste Testfallgruppe in exakter Form:
0
0
0
46375/10296
3/2
1792/1025
77/26
49/26
51/13
23345/4433
0
7
0
0
0
Abbildung für den Testfall 5 1 1 3 3 4 4 -3
(die Fläche des grünen Vierecks ist die erwartete Ausgabe):
[ ]
Antworten:
Wolfram Language (Mathematica) , 55 Byte
Probieren Sie es online!
Ein paar Bytes weniger als die einfache Antwort.
Durch Ersetzen
Area
mitDiscretizeRegion
wird die Kreuzung angezeigt.Dies funktioniert übrigens mit allen Simplexen, nicht nur mit Dreiecken.
-1 Byte dank JungHwan Min
@ user202729s Vorschlag fügte 4 Bytes hinzu, lässt es jedoch 0 für entartete Dreiecke ergeben
quelle
{{0,0}}
bis{0{,}}
(dies funktioniert, weil der Ausdruck ausgewertet wird{Times[0, {Null, Null}]}
)Python 2 + PIL,
341318313284270 BytesBesonderer Dank geht an Dennis, der dank Mr. Xcoder sofort PIL auf TIO
-23 Bytes hinzugefügt hat
Probieren Sie es online! oder Probieren Sie alle Testfälle aus
Um die Differenz zu berechnen, werden die Dreiecke buchstäblich gezeichnet und die Anzahl der Pixel überprüft, die in beiden Bildern gezeichnet werden.
Diese Methode hat einen Rundungsfehler eingefügt, der durch Erhöhen der Bildgröße verringert wird.
Erläuterung
quelle