Dreiecks-Beinhaltung

Problem 102

Drei verschiedene Punkte werden zufällig in einer Kartesischen Ebene platziert, für die -1000 ≤ x, y ≤ 1000, sodass ein Dreieck gebildet wird.

Betrachten Sie die folgenden zwei Dreiecke:

A(-340,495), B(-153,-910), C(835,-947)

X(-175,41), Y(-421,-714), Z(574,-645)

Es kann bestätigt werden, dass das Dreieck ABC den Ursprung enthält, wohingegen das Dreieck XYZ dies nicht tut.

Benutzen Sie triangles.txt (Rechtsklick und 'Link/Ziel speichern unter...'), eine 27K Textdatei, welche die Koordinaten von eintausend "zufälligen" Dreiecken enthält, und finden Sie die Anzahl von Dreiecken, für welche das Innere den Koordinatenursprung enthält.

HINWEIS: Die ersten zwei Beispiele der Datei repräsentieren die Dreiecke im Beispiel oben.