Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!
Werbeanzeige
Administrator
C-/C++-Quelltext |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 |
////////////////////////////////////////////////////////////////////////// // spieleprogrammierer.de-Programmier-Contest #03 // // ******************************************************************** // // Titel: ...... "Kreisschnitt" // // Typ: ........ Geschwindigkeit // // Deadline: ... 17.02.2008 // // Abgabe: ..... contest@spieleprogrammierer.de // // ******************************************************************** // // // // Eingabe: // // -------- // // Gegeben sind N Kreise, dargestellt als (x, y, r). // // x und y sind die Koordinaten des Mittelpunkts, r ist der Radius. // // // // Geforderte Ausgabe: // // ------------------- // // Der Inhalt der Fläche A, die entsteht, wenn man alle Kreisflächen // // miteinander schneidet. Diese Fläche besteht also aus allen Punkten, // // die in sämtlichen Kreisen liegen. // // Besteht die Eingabe nur aus einem einzigen Kreis, so ist das // // Ergebnis natürlich der Flächeninhalt dieses Kreises (pi * r²). // // Wird kein Kreis angegeben, so ist 0 korrekt. // // Ebenso ist das korrekte Ergebnis 0, wenn die Kreisflächen keine // // gemeinsamen Punkte haben. // // Ein Ergebnis wird als korrekt angesehen, wenn es vom exakten // // Ergebnis um nicht mehr als 0.05% nach oben oder unten abweicht. // // Eine Referenzimplementierung gibt es diesmal nicht, sondern nur // // einige ausgewählte Tests. // // // // Randbedingungen: // // ---------------- // // N <= 10000 // // -100 <= x <= 100 // // -100 <= y <= 100 // // 0 <= r <= 100 // // A = 0 oder A >= 0.0001 // // // // Anmerkung zur letzten Bedingung: // // Das heißt: wenn die Schnittfläche existiert, dann ist sie garantiert // // nicht kleiner als 0.0001. // // // ////////////////////////////////////////////////////////////////////////// #include <vector> #include <iostream> #include <iomanip> #include <cmath> #include <ctime> ////////////////////////////////////////////////////////////////////////// // Konstanten const size_t MAX_NUM_CIRCLES = 10000; const double MIN_X = -100.0; const double MAX_X = 100.0; const double MIN_Y = -100.0; const double MAX_Y = 100.0; const double MAX_RADIUS = 100.0; const double MIN_AREA = 0.0001; const double TOLERANCE = 0.0005; const double PI = 3.1415926535897932; ////////////////////////////////////////////////////////////////////////// // Hilfsfunktion zum Messen der Zeit inline double time() { return static_cast<double>(clock()) / CLOCKS_PER_SEC; } ////////////////////////////////////////////////////////////////////////// // einfacher Zufallsgenerator (liefert Zufallszahl zwischen 0 und 4294967290) inline unsigned int random() { static unsigned long long int seed = 4284567975ULL; const unsigned int value = static_cast<unsigned int>((279470273 * seed) % 4294967291ULL); seed = value; return value; } ////////////////////////////////////////////////////////////////////////// // prüft, ob ein Ergebnis OK ist inline bool is_ok(double result, double correct_result) { const double tolerance = correct_result * TOLERANCE; return fabs(result - correct_result) <= tolerance; } ////////////////////////////////////////////////////////////////////////// // Kreis struct Circle { Circle() { } Circle(double x, double y, double r) : x(x), y(y), r(r) { } double x; // x-Koordinate des Mittelpunkts (MIN_X <= x <= MAX_X) double y; // y-Koordinate des Mittelpunkts (MIN_Y <= y <= MAX_Y) double r; // Radius (0 < r <= MAX_RADIUS) }; ////////////////////////////////////////////////////////////////////////// // Testfall struct TestCase { std::vector<Circle> circles; double correct_result; }; ////////////////////////////////////////////////////////////////////////// // >>> DEINE FUNKTION - BITTE IMPLEMENTIEREN! <<< double my_intersection(const std::vector<Circle>& circles) { return 0.0; } ////////////////////////////////////////////////////////////////////////// int main() { std::vector<TestCase> test_cases; // gar kein Kreis TestCase tc1; tc1.correct_result = 0.0; test_cases.push_back(tc1); // ein einzelner Kreis TestCase tc2; tc2.circles.push_back(Circle(0.0, 0.0, 0.5)); tc2.correct_result = 7.853981634e-1; test_cases.push_back(tc2); // zwei Kreise, die sich nicht schneiden TestCase tc3; tc3.circles.push_back(Circle(0.0, 0.0, 0.5)); tc3.circles.push_back(Circle(1.0, 1.0, 0.5)); tc3.correct_result = 0.0; test_cases.push_back(tc3); // drei konzentrische Kreise TestCase tc4; tc4.circles.push_back(Circle(0.0, 0.0, 1.0)); tc4.circles.push_back(Circle(0.0, 0.0, 0.5)); tc4.circles.push_back(Circle(0.0, 0.0, 0.25)); tc4.correct_result = 1.9634954085e-1; test_cases.push_back(tc4); // zwei Kreise, die sich mandelförmig schneiden TestCase tc5; tc5.circles.push_back(Circle(0.0, 0.0, 1.0)); tc5.circles.push_back(Circle(1.0, 0.0, 1.0)); tc5.correct_result = 1.2283696986; test_cases.push_back(tc5); // wie Testfall 5, aber mit einem kleinen Kreis komplett innerhalb der Schnittfläche TestCase tc6; tc6.circles.push_back(Circle(0.0, 0.0, 10.0)); tc6.circles.push_back(Circle(10.0, 0.0, 10.0)); tc6.circles.push_back(Circle(0.5, 0.0, 0.25)); tc6.correct_result = 1.9634954085e-1; test_cases.push_back(tc6); // vier gleich große Kreise auf einem Quadrat angeordnet TestCase tc7; tc7.circles.push_back(Circle(0.0, 0.0, 10.0)); tc7.circles.push_back(Circle(10.0, 0.0, 10.0)); tc7.circles.push_back(Circle(0.0, 10.0, 10.0)); tc7.circles.push_back(Circle(10.0, 10.0, 10.0)); tc7.correct_result = 3.1514675194e1; test_cases.push_back(tc7); // wie Testfall 7, aber mit einem kleinen Kreis komplett innerhalb der Schnittfläche TestCase tc8; tc8.circles.push_back(Circle(0.0, 0.0, 10.0)); tc8.circles.push_back(Circle(10.0, 0.0, 10.0)); tc8.circles.push_back(Circle(0.0, 10.0, 10.0)); tc8.circles.push_back(Circle(10.0, 10.0, 10.0)); tc8.circles.push_back(Circle(5.0, 5.0, 0.01)); tc8.correct_result = 3.1415926536e-4; test_cases.push_back(tc8); // zwei identische Kreise TestCase tc9; tc9.circles.push_back(Circle(50.0, -70.0, 100.0)); tc9.circles.push_back(Circle(50.0, -70.0, 100.0)); tc9.correct_result = 3.1415926536e4; test_cases.push_back(tc9); // vier Kreise, von denen sich drei schneiden TestCase tc10; tc10.circles.push_back(Circle(-1.0, -0.5, 1.0)); tc10.circles.push_back(Circle(1.0, -0.5, 1.0)); tc10.circles.push_back(Circle(0.0, 0.5, 1.0)); tc10.circles.push_back(Circle(0.0, 100.0, 80.0)); tc10.correct_result = 0.0; test_cases.push_back(tc10); std::cout.setf(std::ios::left); for(std::vector<TestCase>::const_iterator it = test_cases.begin(); it != test_cases.end(); ++it) { const double result = my_intersection(it->circles); const bool ok = is_ok(result, it->correct_result); std::cout << "Ergebnis: " << std::setw(15) << result; std::cout << "Korrekter Wert: " << std::setw(15) << it->correct_result; std::cout << (ok ? "OK!" : "Fehler!") << std::endl; } return 0; } |
Administrator
Zitat
// zwei Kreise, die sich nicht schneiden
Administrator
Phili
unregistriert
Mastermind
unregistriert
Administrator
Zitat von »"Mastermind"«
Muss der "zufallszahlengenerator" verwendet werden, der dort steht oder ein beliebiger?
Zitat von »"Mastermind"«
Wenn letzteres:
Darf fremder Code eingebaut werden, sofern er sich nicht in librarys (die ja verboten sind) befindet?
Zitat von »"Mastermind"«
Wird der Evaluationsdatensatz genügend groß sein, das der Gewinner nicht der "beste errater der Testdaten" ist?
Zitat von »"Phili"«
Bei mir klappts .
Allerdings gibts in dem Programmaufbau noch keine Möglichkeit, die Performance zu messen. Wenn ich das Prog aus der IDE ausführ, sagt mir die ne Execution Time von 0.078 s des gesamten Programms.
Werbeanzeige