#09: "Rechtecke"
Typ: Geschwindigkeit
Deadline: 12.10.2008
Abgabe: contest@spieleprogrammierer.de
Bitte beachten:
- Ablauf und Regeln
Aufgabenstellung:
Gegeben ist eine Liste mit Rechtecken, die in ein "Bild" gezeichnet werden sollen. Die Rechtecke werden der Reihe nach gezeichnet. Das heißt, dass ein Rechteck, das weiter hinten in der Liste liegt, ein anderes Rechteck, das weiter vorne in der Liste liegt, überdecken kann. Es wird nicht verlangt, alle Rechtecke komplett zu zeichnen, sondern nur einen gewissen Ausschnitt (kann man sich wie ein Fenster vorstellen).
Rechtecke werden durch
begin_x,
begin_y sowie
end_x und
end_y beschrieben. Achtung: begin_x/y gehört zum Rechteck dazu, end_x/y hingegen nicht (so wie bei STL-Containern). end_x/y ist immer größer als begin_x/y. Übergeben werden ein Zeiger
p_rectangles auf die Rechtecke und ihre Anzahl
num_rectangles.
Der zu zeichnende Ausschnitt (der helle Bereich im Bild unten) wird durch die Position der linken oberen Ecke (view_x, view_y) und die Bildgröße
image_size bestimmt.
Das Bild
p_image ist ein Array von Integern, dessen Pixel zeilenweise aufeinander folgen. Das Pixel an Stelle x, y erhält man also mit p_image[y * image_size + x].
Korrekt ist das Bild, wenn jedes Pixel den Index des am weitesten hinten in der Liste liegenden Rechtecks enthält, das dieses Pixel beinhaltet. Die "Farbe" eines Rechtecks ist also einfach sein Index in der Rechteckliste.
Das klingt vielleicht kompliziert, ist aber eigentlich ganz einfach. Schaut euch die Referenzfunktion reference_painter an. Die zu implementierende Funktion sieht so aus:
|
C-/C++-Quelltext
|
1
2
3
4
5
6
7
8
9
|
// >>> DEINE FUNKTION - BITTE IMPLEMENTIEREN! <<<
void my_painter(const Rectangle* p_rectangles,
uint32_t num_rectangles,
uint32_t* p_image,
uint32_t image_size,
int32_t view_x,
int32_t view_y)
{
}
|
Besonderheiten:
- p_rectangles und p_image sind 16-Byte-ausgerichtet, um mögliche Optimierungen mittels SSE zu vereinfachen.
- num_rectangles liegt zwischen 1 und MAX_NUM_RECTANGLES (10 Millionen).
- image_size ist eine Zweierpotenz und liegt zwischen MIN_IMAGE_SIZE (12
und MAX_IMAGE_SIZE (4096).
- Das erste Rechteck in der Liste überdeckt immer das gesamte Bild ("Hintergrundfarbe" ist 0).
- Für 16-Byte-ausgerichtete Speicherreservierungen, falls ihr welche benötigt, könnt ihr die Funktionen aligned_alloc und aligned_free aus der "utils.h" benutzen.
Bewertung:
Es zählt die Geschwindigkeit. Jede Lösung muss einen bestimmten Testparcours durchlaufen. Für jede Aufgabe werden Punkte entsprechend der benötigten Zeit verteilt. Wer am Ende die meisten Punkte hat, gewinnt. Die Aufgaben unterscheiden sich durch die Anzahl der Rechtecke, die Bildgröße und möglicherweise leicht durch die Verteilung der verschiedenen Rechtecktypen (zufällige Rechtecke, Punkte, Linien).
Paket hier herunterladen
Viel Spaß!
Zitat von »"David Scherfgen"«
20.04.2024, 04:50
Zum Seitenanfang
