Eine Woche Programmierwettbewerb: Rechtecke

paar fragen:
wieso machst du eckige klammern auf die du dann mit runden klammern schließt?
wie ist der "größte index" definiert? index im rectangles-vector?
bedeutet "jeder punkt" jedes integer zwischen min und max für x und y?

SG1

[) schrieb:

wieso machst du eckige klammern auf die du dann mit runden klammern schließt?

Weil es um halb-offene Intervalle geht.

ok. sry wenn die fragen doof sind, ich habs ned so mit mathe, insb. ned mit notationen.

die aufgabe sieht leicht aus, kann mal jemand kurz sagen wo die schwierigkeit liegt?

Korbinian

Hi,

in Java analog:

public interface PontoContest {
    void algorithm(Rectangle plane, ArrayList<Rectangle> rects, ArrayList<Integer> result);
}

Headhunter

Korbinian schrieb:

Hi,

in Java analog:

public interface PontoContest {
    void algorithm(Rectangle plane, ArrayList<Rectangle> rects, ArrayList<Integer> result);
}

Sicher? Müsste "results" nicht zweidimensional sein? Also so:

public interface PontoContest {
    void algorithm(Rectangle plane, ArrayList<Rectangle> rects, ArrayList<ArrayList<Integer>> result);
}

OT: Muss man eigentlich immer noch so auf "result" zugreifen? result.elementAt(x).elementAt(y)

Jester

der letzte Parametertyp sollte eher ArrayList<ArrayList<Integer>> heißen, oder?

Korbinian

Jap, ihr habt Recht.

Headhunter

Ich habe eben mal eine lauffähige Version mit Ruby erzeugt - ist das außer Konkurrenz?

Ponto: Hast du vielleicht noch ein paar mehr Testdaten mit korrekten Ausgaben?

Jester

Wenn Du nen Generator schreibst und hier postest, dann poste ich meinen simplen Algorithmus, der so stupide ist, dass er garantiert nix falsch macht.

Headhunter

Generator? Nööö, da habe ich zwar auch schon dran gedacht, aber noch nichts programmiert. Was ich meinte war, ist dass ich ne Lösung in Ruby statt C++/Java geschrieben habe.
Und was fürn Algorithmus meinst du ?

Jester

Mein Vorschlag: Du schreibst nen Generator (damit haben wir ne Beispielquelle) und ich rücke dafür einen Lösungsalgorithmus raus, der zwar lahm ist, aber garantiert richtig.

jenz

@jester: Einen Generator für Zufallsrechtecke???

Mehr muss er (oder besser du) nicht machen, wenn deine Lösung wirklich keine Fehler macht, dann kannst du doch darauf gleich die Ausgabe erzeugen.

Und eine paar Zufallsrechtecke zu erzeugen sollte nun wirklich nicht sooo schwer sein, oder?

Also eigentlich bietet sich doch an, dass du (Jester) den Generator schreibst.

Sorry, aber liegt einfach so auf der Hand.

Grüße,
Jenz

PS. ich werde auch eine Lösung zusammentickern und natürlich nicht die offensichtliche triviale.
Aber besser als O(N) wird man von der Komplexität wohl nicht werden können...
Aber das ist ja auch nicht gefragt, sondern eine schnelle Lösung... auch wenn sich das meistens gegenseitig bedingt.

otze

Aber besser als O(N) wird man von der Komplexität wohl nicht werden können...

kommt drauf an, welches N du meinst

jenz

@jester: okay, dann mache ich das.

@otze: ich sehe da nur eine veränderliche und du?

jenz

otze

jenz schrieb:

@otze: ich sehe da nur eine veränderliche und du?

ich sehe 2, wobei die eine teilmenge der anderen ist

jenz

das hier könnte doch ein guter anfang für einen generator sein:

void generate_rectangles(Rectangle plane,std::vector<Rectangle> &rectangles) {
  unsigned int width(plane.maxx-plane.minx);
  unsigned int height(plane.maxy-plane.miny);
  unsigned int number(rand() & 10000);
  rectangles.resize(number);
  for (int i(0);i<number;++i) {
    Rectangle &r(rectangles[i]);
    r.minx = rand()%width;
    r.maxx = r.minx+rand()%(width-r.minx);
    r.miny = rand()%height;
    r.maxy = r.miny+rand()%(height-r.miny);
  }
}

leider muss ich jetzt weg. ist ungetestet, aber compiliert...

Heute Abend geht es weiter.

Jens

Jester

Die Rechtecke dürfen laut Aufgabenstellung auch über die fragliche Ebene überstehen. Solche Testfälle sollten auch mitgeneriert werden. Codetags wären prima, so isses ein bißchen schwer zu lesen.

Ich schau, dass ich meinen Algo heute abend irgendwann poste.

jenz

ach ja, darf überstehen,
das macht es beim generieren ja noch viel einfacher...
mit der rechten grenze war ich mir jetzt noch nicht ganz sicher, aber dann klärt sich das ja viel einfacher

code tags sind schon drin.

Ponto

[) schrieb:

paar fragen:
wieso machst du eckige klammern auf die du dann mit runden klammern schließt?
wie ist der "größte index" definiert? index im rectangles-vector?
bedeutet "jeder punkt" jedes integer zwischen min und max für x und y?

Deine zweite Frage: Der Index eines Rechtecks ist der Index im Rectangles Vektor. Der größte davon zählt.
Deine dritte Frage: Die verstehe ich nicht ganz. Zum Rechteck [minx, maxx) x [miny, maxy) gehören alle (x, y) für die gilt minx <= x < maxx und miny <= y < maxy.

Ponto

Headhunter schrieb:

Ich habe eben mal eine lauffähige Version mit Ruby erzeugt - ist das außer Konkurrenz?

Ponto: Hast du vielleicht noch ein paar mehr Testdaten mit korrekten Ausgaben?

Man kann es mitlaufen lassen. Ich poste bald (wahrscheinlich Donnerstag) den Testcode. Dann kann man den auf Ruby portieren. Das müssen die Java Jungs dann auch machen.