WPC-Aufgabe (Programmierwettbewerb)

Herzlichen Glückwunsch evilissimo!!!!

Schade das nur so wenig mitgemacht haben. Und das obwohl Weihnachten war.

So,wie jeder der sich mein programm mal angesehen hat vielleicht gesehen hat baut das programm einen BSP tree.Also im Prinzip einen Binaerbaum,wo eine linie in einem Knoten gespeichert wird und rechter und linker unterbaum nur linien enthalten die rechts/links von der linie liegen.Daher hat man im besten fall logarithmische kosten zum durchsuchen nach schnittpunkten.
Also halten wir fest eine Strecke teilt die Ebene in 2 Halbebene und die Trennlinie ist die durch die Strecke verlaufende Gerade. Strecken die diese Gerade schneiden werden geteilt und es wird ggf. als Schnittpunkt gezaehlt (je nachdem ob es auf der Strecke liegt oder nur auf der verlaengerten Gerade.
Soweit so gut,ein fundamentales Problem sind allerdings Strecken die auf ein und der selben Gerade liegen. Hier kann man nicht sagen ob sie in den rechten oder linken unterbaum eingefuegt werden muessen. Fuegt man sie in nur einen Unterbaum ein, kann es passieren, dass eine andere Strecke auf der anderen Seite liegt und trotzdem genau bis zur trennenden Gerade verlaeuft (diese also beruehrt). Das waere dann aber ein Schnittpunkt mit der Strecke die nun genau im falschen Unterbaum eingefuegt wurde,er wuerde also nicht gezaehlt. Fuegt man die problematische Strecke in beide Unterbaeume ein, so wird eine andere Strecke an der Gerade geteilt und fuehrt zu 2 schnittpunkten,also wieder falsch.

Meine erste Loesung war es diese boesen Strecken gar nicht einzufuegen,sondern in einen array zu packen und dann extra zu pruefen. Das ist zwar langsam,aber sollte ein extrem seltener Sonderfall sein. So nun aber ein Gegenbeispiel wo dies nicht korrekt ist: Folgende einfuegereihenfolge:
1. eine Senkrechte Strecke sagen wir (0,-1)-(0,1)
2. eine waagerechte (1,0)-(2,0)
3. eine waagerechte (-2,0)-(-1,0)
4. eine waagerechte (-0.5,0)-(0.5,0)
so was passiert also? nach 1-3. hat man einen Baum mit 1. in der wurzel und 2.,3. als rechtes/linkes kind. Nun soll 4 eingefuegt werden. 4 schneidet 1. wird also geteilt,nun soll (-0.5,0)-(0,0) und (0,0)-(0.5,0) in 3 bzw 4 eingefuegt werden,die liegen beide auf der jeweils trennenden Gerade,also werden beide als boese Linien gespeichert und nicht eingefuegt. Nun wird zum schluss deren Schnitt geprueft, jede der boesen linien schneidet 1. also 2 extra schnittpunkte,also werden 3 gezaehlt obwohl nur einer da ist!

behoben kann das werden indem man z.b. durch eine exception signalisiert das eine boese linie aufgetreten ist,und dann alle linien und schnittpunkte die durch sie entstanden sind wieder entfernt werden oder so,dafuer hatte ich aber keine zeit mehr...

wann kommt denn die nächste aufgabe? ich möchte euch mal so richtig an die wand proggen.

Jester

Gibt's denn noch mehr Interessenten?

Ponto

Jester schrieb:

Gibt's denn noch mehr Interessenten?

Immer.

Brutus

Jop.

lohnt sich aber nur wenn volkard auch mitmacht.

Aufgabe: Programmiert Doom 4 und schickt die fertigen Programme an...

Soll ich das jetzt schreiben oder ist das zu schlecht.

PeterTheMaster

interesse ja, zeit weiss nicht.

ich progge euch alle an die wand ey

Wie kann man jemand an die Wand proggen?

Geht das mit C oder muss ich C++ verwenden? Kann einer mal ein Beispiel für and die Wand proggen posten?

cout << hello wört

PeterTheMaster

sei x ein verb. der ausspruch "ich x'e dich an die wand!" heisst soviel wie "ich bilde mir ein, im x'en sehr viel besser zu sein als du.".
woher diese metapher allerdings kommt, ist mir gerade nicht ganz klar. gibt es in irgendeiner sportart eine wand?

setX("wx");
pronounceX(); // wichs

cu frau ulle

Ich hätte auch mal Lust mitzumachen

Beim Squash gibt es ne Wand.

Jäster schrieb:

Aufgabe: Programmiert Doom 4 und schickt die fertigen Programme an...

Soll ich das jetzt schreiben oder ist das zu schlecht.

Hier schonmal das Främework: (funzt aber noch nicht so ganz)

#include <iostream.h>

class doom4
{
    bool Load();
};

bool doom4::Load()
{
 //<-- hier Code einfügen
 return false;
}

void main(void)
{
    doom4 doom3;
    if(!doom3.Load()) cout<<"Could not load Doom4"<<endl;
    return;
}

Jester

Progga schrieb:

(funzt aber noch nicht so ganz)

Wenn Du Load private lassen willst solltest Du main als friend deklarieren, dann funktioniert es!