spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

C-/C++-Quelltext

//////////////////////////////////////////////////////////////////////////

// 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;
}