Kurzbeschreibung:

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 Konvhuel.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.3.1_1) 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:

Eine konvexe Hülle ist, kurz gesagt, die Menge der kürzesten Pfade, die die gesamte Punktmenge umschließen. Die Ecken dieser Polygon-Hülle sind Grenzpunkte aus der ursprünglichen Punktmenge. Punkte, die auf einer Verbindung zweier Punkte der konvexen Hülle liegen, sind ebenfalls Punkte der konvexen Hülle.

Ein anschauliches Beispiel:

Um diese Aufgabe zu lösen, beginnen Sie mit dem Polygon, das aus den ersten drei Punkten besteht. Überprüfen Sie, ob der nächste Punkt außerhalb dieses Polygons liegt. Wenn ja, passieren zwei Sachen: Der neue Punkt wird (vorerst) in die Hülle aufgenommen (die geeignete Stelle in der Liste finden Sie dadurch, daß sich die Strecken der Hülle nicht schneiden dürfen.)

Weiters wird überprüft, ob ältere Punkte aus der Hülle wieder entfernt werden müssen. Dazu überprüfen Sie für jeden Punkt der Hülle, ob er im Polygon liegt, das aus den anderen Punkten der Hülle gebildet wird. Wenn die Hülle z.B. aus (A,B,C,D) besteht und nun Punkt E hinzukommt, dann muß geprüft werden, ob A in (B,C,D,E) liegt, ob B in (A,C,D,E) liegt etc.

Diesen Vorgang wiederholen Sie für alle Punkte.

Eingabedaten:

Die Eingabe wird durch ein beliebiges Zeichen, das statt einer neuen x-Koordinate eingegeben wird, abgeschlossen.

Ausgabedaten:

Sortieren Sie die Punkte aufsteigend nach der X-Koordinate, innerhalb gleicher X aufsteigend nach Y.

Geben Sie am Ende einen Zeilenvorschub aus.

Fehlerbehandlung:

Lesen Sie aber auf jeden Fall solange Zahlen ein, bis ein Endezeichen kommt.

Beispiele:

Eingabedaten

-1 -1 1 2 2 2 1 1 3 1 -1 0 -2 -2 x 0 0 5 5 5 0 x

Ausgabedaten

(-2,-2) (-1,0) (1,2) (2,2) (3,1) (0,0) (5,0) (5,5)

Testen:

java Konvhuel < Konvhuel.i1 > Konvhuel.out1

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