3154	Konvneck	konvexes Vieleck
Kategorie: Grafik Klasse: schwer Eingabe: siehe Spezifikation Ausgabe: siehe Spezifikation
Abzugebende Files: Konvneck.txt, Konvneck.java, *.java

Kurzbeschreibung:

Die Eckpunkte eines Vielecks werden eingelesen; es wird überprüft, ob die Kanten des Vielecks einander schneiden. Wenn dies nicht der Fall ist, wird festgestellt, ob das Vieleck konvex ist.

Allgemeine Hinweise:

• Sie haben Lösungen (und Spezifikationen) aus der 1. Runde von anderen Studenten erhalten, die Ihnen Ihre Aufgabe erleichtern sollen. Wählen Sie eine Lösung aus, die Ihnen hinsichtlich Lesbarkeit, Programmierstil, Korrektheit und Verwendbarkeit am besten erscheint. Verwenden Sie diese Lösung in Ihrem Programm. Sie können auch die anderen Lösungen einsetzen.
• Merken Sie sich die Lösungsnummer des ausgewählten Beispieles für die Abgabe. Diese Nummer müssen Sie bei der Abgabe angeben. Geben Sie nur jene Lösungsnummer an, die Sie auch wirklich ausgewählt haben.
• Erstellen Sie für alle Lösungen zu diesem Beispiel (siehe: "Abzugebende Files") ein File mit dem Namen <number>.txt. und schreiben in dieses File ein Review (=Kritik) zu der Lösung. Diese Reviews erhalten dann die TeilnehmerIn von dem/der die Lösung stammt. Beachten Sie das bitte bei der Form Ihrer Kritik.
• Sie können für die Lösung der gewählten Aufgabe eine oder mehrere Klassen programmieren. Die Klasse Konvneck.java muß aber die Methode main enthalten. Weiters müssen alle abgegebenen Klassenfiles in demselben Verzeichnis vorliegen, Pfadangaben sind nicht gestattet.
• Achten Sie auf die korrekten Konventionen der Groß/Kleinschreibung bei Klassen und Methoden!
  [Wir tun das jetzt auch :-)]
• Falls Ihre Lösung einen Exit Code zurueckliefert, so achten Sie darauf, dass dieser den Wert 0 hat. Bei allen anderen Werten können Probleme bei der Bewertung und in weiterer Folge unbeabsichtigte Punkteabzüge auftreten.
• Ihre Lösung darf nur genau jene Ausgabedaten liefern, die in der Spezifikation verlangt werden. Die Ausgaben Ihrer Lösung werden automatisch mit Referenzdaten verglichen; etwaige Abweichungen führen zu Punkteabzügen!
• Testen Sie Ihre Lösung vor der Abgabe mit der mitgelieferten Eingabedatei. Geben Sie Ihre Lösung erst ab, wenn die Ausgaben Ihrer Lösung mit der ebenfalls mitgelieferten Ausgabedatei übereinstimmen! Testen Sie Ihre Lösung auch mit anderen Eingabedaten.
• Verwenden Sie nur das von uns mitgelieferten Package eprog für Ihre Ein/Ausgaben. Klassen, die Packages oder Klassen ausserhalb der verwendeten Übungsumgebung (Java2, Standard Edition, Version 1.5.0) verwenden, können von uns nicht getestet werden und werden daher mit 0 Punkten bewertet!
• Schreiben Sie Ihre Klasse(n) möglichst allgemein und kommentieren Sie diese gut. Erstellen Sie weiters eine übersichtliche und verständliche Dokumentation. Damit erhöhen Sie Ihre Chancen, daß andere Studenten in der nächsten Runde Ihre Lösung wählen und Ihnen damit zu Zusatzpunkten verhelfen!

Aufgabenstellung:

Lesen Sie die Koordinatenpaare der Eckpunkte eines Vielecks ein. Prüfen Sie, ob sich zwei Kanten des Vielecks schneiden, wie dies im folgenden Beispiel der Fall ist:

(0,0) (2,0) (2,4) (4,4) (4,2) (0,2)

Wenn dies nicht der Fall ist, stellen Sie fest, ob das Vieleck konvex ist (daß heißt, das alle Innenwinkel<180° sind). Dazu sollen Sie wie folgt vorgehen:

Seien P1, P2, ..., Pn die Eckpunkte des Vielecks. Ermitteln Sie die Lage des Punktes P3 bezüglich der Gerade, die durch P1 und P2 geht (verwenden Sie dazu das Programm aus der ersten Runde). Wenn dieser Punkt LINKS liegt, dann muß auch P4 links bezüglich (P2,P3) liegen, P5 links bezüglich (P3,P4), ..., Pn bez. (Pn-2,Pn-1), P1 bez. (Pn-1,Pn) und P2 bez. (Pn, P1).

Klarerweise gilt die Umkehrung, wenn P3 RECHTS bezüglich (P1,P2) liegt: Dann muß auch P4 RECHTS bez. (P2,P3) liegen usw.

Wenn einer der Punkte AUF der Geraden seiner Vorgängerpunkte liegt, dann ist der Eingabedatensatz fehlerhaft (weil einer der Punkte gar kein Eckpunkt ist).
ACHTUNG: Diese Bedingung muß von Ihrem Programm auch dann überprüft werden, wenn Sie festgestellt haben, daß sich zwei Kanten schneiden!

Eingabedaten:

Lesen Sie die Koordinatenpaare des Vielecks als Strings ein, die folgenden Aufbau haben müssen: "(x,y)" wobei x und y Zahlen sind (z.B. "(-5.5,2.75)" ). Die eingelesenen x- und y-Koordinaten müssen im Bereich [-100,100] liegen.

Der Datensatz wird durch das Zeichen "=", das anstatt eines neuen Koordinatenpaares eingegeben wird, abgeschlossen. Es müssen mindestens 3 und maximal 15 Koordinatenpaare eingegeben werden. Die oben genannte Bedingung, daß keiner der Eckpunkte auf der Gerade seiner Vorgänger liegen darf, muß erfüllt sein.

Ausgabedaten:

Bei korrekten Eingabedaten soll Ihr Programm "SCHNEIDET" ausgeben, wenn sich mindestens zwei Kanten schneiden, "KONVEX", wenn sich keine Kanten schneiden und das Vieleck konvex ist und "KONKAV", wenn sich keine Kanten schneiden und das Vieleck nicht konvex ist.

Geben Sie danach einen Zeilenvorschub aus.

Fehlerbehandlung:

Genügen die eingegebenen Daten nicht den Bedingungen, so soll Ihr Programm die Meldung "FALSCHE EINGABE", gefolgt von einem Zeilenvorschub, ausgeben.

Es sind aber solange Strings einzulesen, bis das Abschlußzeichen "=" eingegeben wird.

Beispiele:

Eingabedaten

(0,0) (2,0) (2,4) (4,4) (4,2) (0,2) = (0,0) (2,0) (4,2) (4,4) (2,4) (0,2) =

Ausgabedaten

SCHNEIDET KONVEX

Testen:

Diese Beispiele dienen nur zur Verdeutlichung der Spezifikation und müssen nicht korrekt formatiert sein. Die korrekte Formatierung entnehmen Sie bitte dem mitgelieferten Outputfile. Zum Testen Ihrer Lösung können Sie aus den mitgelieferten Eingabedaten wie folgt eine Ausgabedatei erzeugen:

java Konvneck < Konvneck.i1 > Konvneck.out1

Das erzeugte File Konvneck.out1 können Sie dann mit dem mitgelieferten Outputfile Konvneck.o1 vergleichen.