HS12MBR.cpp

#include <iostream>
#include <string>
#include <vector>
#include <memory>
using namespace std;

class TwoDidemsionObject
{
    public: virtual ~TwoDidemsionObject() {}
};

class Point : public TwoDidemsionObject
{
public:
    Point() {}
    Point(int x_, int y_) : x(x_), y(y_) {}

    static const char Id;
    int x;
    int y;
};

class Line : public TwoDidemsionObject
{
public:
    Line(shared_ptr<Point> begin_, shared_ptr<Point> end_): begin(begin_), end(end_) {}

    static const char Id;
    shared_ptr<Point> begin;
    shared_ptr<Point> end;
};

class Circle : public TwoDidemsionObject
{
private:
    shared_ptr<Point> _bottomLeft;
    shared_ptr<Point> _topRight;
public:
    Circle(shared_ptr<Point> center_, int radius_): center(center_), radius(radius_) {}

    static const char Id;
    shared_ptr<Point> center;
    int radius;

    shared_ptr<Point> getBottomLeft()
    {
        if (_bottomLeft == nullptr)
        {
            _bottomLeft = make_shared<Point>(center->x - radius, center->y - radius);
        }
        return _bottomLeft;
    }

    shared_ptr<Point> getTopRight()
    {
        if (_topRight == nullptr)
        {
            _topRight = make_shared<Point>(center->x + radius, center->y + radius);
        }
        return _topRight;
    }
};

const char Point::Id = 'p';
const char Line::Id = 'l';
const char Circle::Id = 'c';

class MinimumBoundRectangle
{
private:
    void selfExpandToPoint(shared_ptr<Point> point)
    {
        if (bottomLeft->x <= point->x && point->x <= topRight->x &&
            bottomLeft->y <= point->y && point->y <= topRight->y)
        {
            return;
        }

        if (point->x < bottomLeft->x)
        {
            bottomLeft->x = point->x;
        }
        else
        {
            topRight->x = point->x;
        }

        if (point->y < bottomLeft->y)
        {
            bottomLeft->y = point->y;
        }
        else
        {
            topRight->y = point->y;
        }
    }
    
    void selfExpandToLine(shared_ptr<Line> line)
    {
        selfExpandToPoint(line->begin);
        selfExpandToPoint(line->end);
    }
    
    void selfExpandToCircle(shared_ptr<Circle> circle)
    {
        selfExpandToPoint(circle->getBottomLeft());
        selfExpandToPoint(circle->getTopRight());
    }

public:
    bool notYetInit = true;
    shared_ptr<Point> bottomLeft = nullptr;
    shared_ptr<Point> topRight = nullptr;

    void init(shared_ptr<TwoDidemsionObject> tdObject) {
        shared_ptr<Point> point = nullptr;
        shared_ptr<Line> line = nullptr;
        shared_ptr<Circle> circle = nullptr;

        if ((point = dynamic_pointer_cast<Point>(tdObject)) != nullptr) {
            bottomLeft = make_shared<Point>(point->x, point->y);
            topRight = make_shared<Point>(point->x, point->y);
        } else if ((line = dynamic_pointer_cast<Line>(tdObject)) != nullptr) {
            auto xMin = line->begin->x < line->end->x ? line->begin->x : line->end->x;
            auto yMin = line->begin->y < line->end->y ? line->begin->y : line->end->y;
            auto xMax = line->begin->x > line->end->x ? line->begin->x : line->end->x;
            auto yMax = line->begin->y > line->end->y ? line->begin->y : line->end->y;
            bottomLeft = make_shared<Point>(xMin, yMin);
            topRight = make_shared<Point>(xMax, yMax);
        } else {
            circle = dynamic_pointer_cast<Circle>(tdObject);
            bottomLeft = make_shared<Point>(circle->getBottomLeft()->x, circle->getBottomLeft()->y);
            topRight = make_shared<Point>(circle->getTopRight()->x, circle->getTopRight()->y);
        }
        notYetInit = false;
    }

    void selfExpand(shared_ptr<TwoDidemsionObject> tdObject) {
        shared_ptr<Point> point = nullptr;
        shared_ptr<Line> line = nullptr;
        shared_ptr<Circle> circle = nullptr;
        
        if ((point = dynamic_pointer_cast<Point>(tdObject)) != nullptr) {
            selfExpandToPoint(point);
        } else if ((line = dynamic_pointer_cast<Line>(tdObject)) != nullptr) {
            selfExpandToLine(line);
        } else {
            circle = dynamic_pointer_cast<Circle>(tdObject);
            selfExpandToCircle(circle);
        }
    }
};

class HS12MBR
{
private:
    vector<vector<shared_ptr<TwoDidemsionObject>>> testCases;
    vector<shared_ptr<MinimumBoundRectangle>> mbrs;

    void readInput()
    {
        int numOfTc;
        cin >> numOfTc;
        for (int i = 0; i < numOfTc; i++)
        {
            int numOfObjects;
            cin >> numOfObjects;
            vector<shared_ptr<TwoDidemsionObject>> testCase;
            for (int j = 0; j < numOfObjects; j++)
            {
                char objectId;
                cin >> objectId;
                if (objectId == Point::Id)
                {
                    int x, y;
                    cin >> x >> y;
                    testCase.push_back(make_shared<Point>(x, y));
                }
                else if (objectId == Line::Id)
                {
                    int x1, y1, x2, y2;
                    cin >> x1 >> y1 >> x2 >> y2;
                    testCase.push_back(make_shared<Line>(make_shared<Point>(x1, y1), make_shared<Point>(x2, y2)));
                }
                else
                {
                    int x, y, radius;
                    cin >> x >> y >> radius;
                    testCase.push_back(make_shared<Circle>(make_shared<Point>(x, y), radius));
                }
            }
            testCases.push_back(testCase);
        }
    }

    void calculate()
    {
        for (const auto& testCase : testCases)
        {
            auto mbr = make_shared<MinimumBoundRectangle>();
            for (const auto& tdObject : testCase)
            {
                if (mbr->notYetInit)
                {
                    mbr->init(tdObject);
                }
                else
                {
                    mbr->selfExpand(tdObject);
                }
            }
            mbrs.push_back(mbr);
        }
    }

    void printResult()
    {
        for (const auto& mbr : mbrs)
        {
            cout << mbr->bottomLeft->x << " " 
                 << mbr->bottomLeft->y << " " 
                 << mbr->topRight->x   << " " 
                 << mbr->topRight->y   << endl;
        }
    }

public:
    void solve()
    {
        readInput();
        calculate();
        printResult();
    }
};

int main()
{
    HS12MBR hs12mbr;
    hs12mbr.solve();
    /*
    Input:
        3
        1
        p 3 3 

        2
        c 10 10 20
        c 20 20 10

        1
        l 0 0 100 20

    Output:
        3 3 3 3 
        -10 -10 30 30
        0 0 100 20
    */

    return 0;
}