the sides of the square may not be parallel to the sides of the field

If you are solving through comparing Min and Max distance from some border point to center of figure, then check for circle in following way: Max - Min <= 3.

Some authors solved this problem with very good time and very small memory. But if we store input data without compressing it is necessary near 1Mb. Maybe there exist solution without storing input at all?
Who can help me to understand how it is possible?

Help! What is in the test 26?

got AC but for the following rectangle ((12, 0), (100, 12), (88, 100), (0, 88)) - you can shift it in any position, my solution will choose 'circle'

#include <iostream>
using namespace std;

#include <list>
#include <vector>
#include <cmath>

namespace grid {
    struct Graph {

        void SafeFree();

        void SetVertexCount(int count);

        int GetVertexCount() const {
            return m_vertexCount;
        }

        Graph();

        ~Graph() {
            SafeFree();
        }

        void SetWeight(short weight, int i, int j);

        short GetWeight(int i, int j) const;


        void TopologicalSortingVariantOne(std::vector<int> &out) const;

        void GetMaximumWeightedPath(std::vector<int> &out);

    private:
        int m_vertexCount;
        std::list<int> *edgelists;
        short **adj;
        short *in;
        short *out;
        int steps;
        bool invalid_edge_lists;

    };



    struct Point2D {
        Point2D ();
        Point2D (double x, double y);
        Point2D operator - (const Point2D &other) const;

        bool operator != (const Point2D &other) const {
            return fabs(other.x - x) > 1e-9 || fabs(other.y - y) > 1e-9;
        }

        double x, y;
    };

    struct Polygon {
        std::vector<Point2D> polyline;

        bool IsDisconnected() {
            return polyline[polyline.size() - 1] != polyline[0];
        }

        void SetSize(int size) {
            polyline.resize(size);
        }

        unsigned GetSize() const {
            return polyline.size();
        }

        void SetPoint(int index, const Point2D &point) {
            polyline[index] = point;
        }

        void PushPoint(Point2D &point) {
            polyline.push_back(point);
        }

        Point2D GetPoint(int index) const {
            return polyline[index];
        }
    };

    struct Line2D {
        Line2D (const Point2D &A, const Point2D &B);
        Point2D A, B;
    };


    struct Vector {
        int xdir;
        int ydir;

        int xSource, ySource;
    };

    typedef std::list<Vector> BoundVectorList;
    typedef BoundVectorList* BoundVectorListPtr;

    struct GridVectorField {
        int lines, columns;

        GridVectorField(int lines, int columns);

        GridVectorField () {
            grid = 0;
            Reset(0, 0);
        }

        void Reset(int lines, int columns) {
            Clear();
            this->lines = lines;
            this->columns = columns;
            grid = new BoundVectorListPtr[lines * columns];
            memset(grid, 0x0, lines * columns * sizeof(BoundVectorListPtr));
        }

        void ClearSparseLists() {
        }

        ~GridVectorField () {
            Clear();
        }

        void AddVector(int i, int j, Vector &vector);
        void ClearVector( int i, int j );

        BoundVectorListPtr GetVectorList(int i, int j) const;

        void Clear();


    private:
        std::list<BoundVectorListPtr> sparseLists;
        BoundVectorListPtr *grid;
    };


    class GridVectorization
    {
    public:


    private:
        double distance2(const Point2D &P,const  Line2D &line) const ;

        double length_squared(const Point2D &A,const  Point2D &B);

        double distance1(const Point2D &A,const  Point2D &B);

        double dot(const Point2D &A,const  Point2D &B);

        double minimum_distance(const Point2D &v,const  Point2D &w,const Point2D &p);

        double cross(const Point2D &  p1, const Point2D &  p2, const Point2D &  p3);

        void BuildGraph(Polygon &inPoly, Graph &outGraph, double const innerTolerance, double const outerTolerance );

    public:
        GridVectorization(void);
        ~GridVectorization(void);

        void AproximatePolygon(Polygon &inPoly, double const innerTolerance, double const outerTolerance, Polygon &outPoly);

        void AproximatePolygonList(std::list<Polygon *> &listIn, double const innerTolerance, double const outerTolerance, std::list<Polygon *> &listOut);

        void VectorizeGrid( char *grid, int const Lines, int const Columns, int const aabbWidth, int const aabbHeight, std::list<Polygon *> &polylistOut );

        void Fill(char *grid, int const i, int const j, int const aabbWidth, int const aabbHeight, int const Lines, int const Columns, int searchValue, int fillValue);

    private:
        char GetCell(int i, int j, char *grid, int Lines, int Columns);

        void SetCell(int i, int j, char *grid, int Lines, int Columns, char cell);

        void DetectPolygon (char *grid, int const i, int const j, int const Lines, int const Columns, GridVectorField &field, Polygon &outPoly);

        void BuildCwVectorField(char *grid, int const Lines, int const Columns, int searchValue, GridVectorField &fieldOut);

        void BuildCcwVectorField(char *grid, int const Lines, int const Columns, int searchValue, GridVectorField &fieldOut);

        void FillAndBuildVectorField(char *grid, int const i, int const j, int const Lines, int const Columns, int searchValue, int fillValue, GridVectorField &fieldOut);

        void FillAndClearVectorField(char *grid, int const i, int const j, int const Lines, int const Columns, int searchValue, int fillValue, GridVectorField &fieldOut);

        bool IsReachable(char *grid, int const Lines, int const Columns, int sourceX, int sourceY, int destX, int destY);


    };
}


#include <iostream>
using namespace std;
using namespace grid;

int main ()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif

    char *grid;
    grid::GridVectorization vectorization;
    int n, m;
    char c;

    scanf("%d%d", &m, &n);
    grid = new char[ n * m ];


    scanf("%c", &c);

    for (int i=0; i<n; ++i)
    {
        for (int j=0; j<m; ++j)
        {
            scanf("%c", &c);
            grid[ m * i + j ] = c - '0';

            //printf("%c", c);
        }
        scanf("%c", &c);
        //printf("\n");
    }


    std::list<Polygon *> poly, poly2;
    vectorization.VectorizeGrid(grid, n, m, 2000, 2000, poly);
    vectorization.AproximatePolygonList(poly, 2, 0.96, poly2);


    Polygon *p = poly2.front();

    switch(p->GetSize())
    {
    case 5:
        printf("square\n");
        break;
    case 4:
        printf("triangle\n");
        break;
    default:
        printf("circle\n");
    }
    return 0;
}

#include <cmath>



namespace grid {

    int dirX[] = {0, 1, 0, -1};
    int dirY[] = {-1, 0, 1, 0};

    char specialGridFlag = char(-1);

    int dirX2[] = {0, 1, 0, -1, 1, 1, -1, -1};
    int dirY2[] = {-1, 0, 1, 0, -1, 1, -1, 1};

    GridVectorization::GridVectorization(void)
    {
    }

    GridVectorization::~GridVectorization(void)
    {
    }

    double GridVectorization::distance2( const Point2D &P, const Line2D &line ) const
    {
        return abs( (line.B.x - line.A.x) * (line.A.y - P.y) - ( line.A.x - P.x ) * (line.B.y - line.A.y) ) /
            sqrt(double((line.B.x - line.A.x) * (line.B.x - line.A.x) + (line.B.y - line.A.y) * (line.B.y - line.A.y)));
    }

    double GridVectorization::length_squared( const Point2D &A, const Point2D &B )
    {
        return (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y);
    }

    double GridVectorization::distance1( const Point2D &A, const Point2D &B )
    {
        return sqrt(length_squared(A, B));
    }

    double GridVectorization::dot( const Point2D &A, const Point2D &B )
    {
        return A.x * B.x + A.y * B.y;
    }

    double GridVectorization::minimum_distance( const Point2D &v, const Point2D &w, const Point2D &p )
    {
        // Return minimum distance between line segment v w and point p
        double l2 = length_squared(v, w);  // i.e. |w-v|^2 -  avoid a sqrt
        if (l2 == 0.0) return distance1(p, v);   // v == w case
        // Consider the line extending the segment, parameterized as v + t (w - v).
        // We find projection of point p onto the line.
        // It falls where t = [(p-v) . (w-v)] / |w-v|^2
        double t = dot(p - v, w - v) / l2;
        if (t < 0.0) return distance1(p, v);       // Beyond the 'v' end of the segment
        else if (t > 1.0) return distance1(p, w);  // Beyond the 'w' end of the segment
        Line2D const &ref = Line2D(w, v);
        return distance2(p, ref);
    }

    double GridVectorization::cross( const Point2D & p1, const Point2D & p2, const Point2D & p3 )
    {
        return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
    }

    void GridVectorization::BuildGraph( Polygon &inPoly, Graph &outGraph, double const innerTolerance, double const outerTolerance )
    {
        outGraph.SetVertexCount(inPoly.GetSize());

        if(!inPoly.GetSize())
            return;

        for(unsigned i=0; i < inPoly.GetSize() - 1; ++i)
            for(unsigned j=1; j < inPoly.GetSize(); ++j) {
                bool ok = true;
                for(unsigned k = i + 1; ok && k < j; ++k) {
                    double min_distance = minimum_distance(inPoly.GetPoint(i), inPoly.GetPoint(j), inPoly.GetPoint(k));
                    double cross_prod = cross(inPoly.GetPoint(j), inPoly.GetPoint(k), inPoly.GetPoint(i));

                    if(min_distance >= innerTolerance && cross_prod <= 0.0) {
                        //cout << "Inner: (" << i << ", " << j << ") - " << k << " distance: " << minimum_distance(inPoly.GetPoint(i), inPoly.GetPoint(j), inPoly.GetPoint(k)) << "\n";
                        ok = false;
                    }
                    if(min_distance >= outerTolerance && cross_prod > 0.0) {
                        //cout << "Outer: (" << i << ", " << j << ") - " << k << " distance: " << minimum_distance(inPoly.GetPoint(i), inPoly.GetPoint(j), inPoly.GetPoint(k)) << "\n";
                        ok = false;
                    }
                }
                if(ok) {
                    outGraph.SetWeight( j - i - 1, i, j );
                }
            }
    }

    void GridVectorization::AproximatePolygon( Polygon &inPoly, double const innerTolerance, double const outerTolerance, Polygon &outPoly )
    {
        Graph polylineGraph;
        BuildGraph(inPoly, polylineGraph, innerTolerance, outerTolerance);
        std::vector <int> optimized;
        polylineGraph.GetMaximumWeightedPath(optimized);

        outPoly.SetSize(optimized.size());

        int last = optimized.size() - 1;

        for(int i = last; i >= 0; --i) {
            outPoly.SetPoint(last - i, inPoly.GetPoint(optimized[i]));
        }
    }

    char GridVectorization::GetCell( int i, int j, char *grid, int Lines, int Columns )
    {
        if(    i < Lines && j < Columns &&
            i >= 0 && j >= 0 &&
            Lines >= 0 && Columns >= 0) {
                return grid[i * Columns + j];
        }
        return 0;
    }

    void GridVectorization::SetCell( int i, int j, char *grid, int Lines, int Columns, char cell )
    {
        if(    i < Lines && j < Columns &&
            i >= 0 && j >= 0 &&
            Lines >= 0 && Columns >= 0) {
                grid[i * Columns + j] = cell;
        }
        //no effect
    }

    void GridVectorization::VectorizeGrid( char *grid, int const Lines, int const Columns, int const aabbWidth, int const aabbHeight, std::list<Polygon *> &polylistOut )
    {
        //detect shapes
        GridVectorField field;

        BuildCwVectorField(grid, Lines, Columns, 1, field);

        int startX = -1, startY = -1;
        for(int i=0; i<Lines; ++i) {
            for(int j=0; j<Columns; ++j) {
                if(grid[i * Columns + j] == 1) {

                    Fill(grid, i, j, aabbWidth, aabbHeight, Lines, Columns, 1, 2);

                    Polygon *newPoly = new Polygon();

                    DetectPolygon(grid, i, j, Lines, Columns, field, *newPoly);
                    //push the polygon
                    polylistOut.push_back(newPoly);

                    //erase the polygon
                    Fill(grid, i, j, Columns, Lines, Lines, Columns, 2, 0);
                }
            }
        }
    }

    void GridVectorization::AproximatePolygonList( std::list<Polygon *> &listIn, double const innerTolerance, double const outerTolerance, std::list<Polygon *> &listOut )
    {
        for(std::list<Polygon *>::iterator it = listIn.begin(); it != listIn.end(); ++it) {
            Polygon *poly = *it;
            if(poly != 0) {
                Polygon *out = new Polygon();
                AproximatePolygon(*poly, innerTolerance, outerTolerance, *out);
                listOut.push_back(out);
            }
        }
    }

    void GridVectorization::DetectPolygon( char *grid, int const i, int const j, int const Lines, int const Columns, GridVectorField &field, Polygon &outPoly )
    {
        ///////////////////calculating the contour of the shape (based on the vector field)////////////////////////////
        BoundVectorListPtr lst = field.GetVectorList(i, j);
        BoundVectorList::iterator it;

        Vector startPos;
        Vector currentPos;

        currentPos.xdir = startPos.xdir = i;
        currentPos.ydir = startPos.ydir = j;

        Vector lastDir;
        lastDir.xdir = -2;
        lastDir.ydir = -2;
        lastDir.xSource = i;
        lastDir.ySource = j;

        Vector currentDir;
        currentDir.xdir = -3;
        currentDir.ydir = -3;

        currentDir.xSource = i;
        currentDir.ySource = j;

        std::list<Point2D> polygon;

        bool error = false;

        int cellValue = GetCell(i, j, grid, Lines, Columns);

        do {

            int ii = (int)currentPos.xdir;
            int jj = (int)currentPos.ydir;

            BoundVectorListPtr lst = field.GetVectorList(ii, jj);
            BoundVectorList::iterator it;

            if(!lst || polygon.size() > (unsigned)((Lines + 1) * (Columns + 1) * 4)) {
                printf("What?\n");
                //fuck
                error = true;
            }

            //first getting the first vector on the contour

            for(it = lst->begin(); it != lst->end(); ++it) {

                if(!IsReachable(grid, Lines, Columns, currentDir.xSource, currentDir.ySource, it->xSource, it->ySource)) continue;

                if(it->xdir == 1 && it->ydir == 0 && GetCell(ii, jj, grid, Lines, Columns) != cellValue) {
                    currentDir = *it;
                    //the vector is an edge

                    break;
                }

                else if(it->xdir == 0 && it->ydir == -1 && GetCell(ii, jj-1, grid, Lines, Columns) != cellValue) {
                    currentDir = *it;
                    //the vector is an edge

                    break;
                }

                else if(it->xdir == -1 && it->ydir == 0 && GetCell(ii-1, jj-1, grid, Lines, Columns) != cellValue) {
                    currentDir = *it;
                    //the vector is an edge

                    break;
                }

                else if(it->xdir == 0 && it->ydir == 1 && GetCell(ii-1, jj, grid, Lines, Columns) != cellValue) {
                    currentDir = *it;
                    //the vector is an edge

                    break;
                }
            }

            //push a vertex only when the direction has changed
            if(lastDir.xdir != currentDir.xdir || lastDir.ydir != currentDir.ydir) {
                polygon.push_back(Point2D(currentPos.xdir, currentPos.ydir));
            }

            lastDir = currentDir;
            currentPos.xdir += currentDir.xdir;
            currentPos.ydir += currentDir.ydir;

        } while ( (startPos.xdir != currentPos.xdir || startPos.ydir != currentPos.ydir) && !error);

        if(error) {
            polygon.clear();
        }
        Polygon *newPoly = &outPoly;
        int k = 0;
        for(std::list<Point2D>::iterator it = polygon.begin(); it != polygon.end(); ++it) {
            newPoly->PushPoint(*it);
            ++k;
        }

        //add the last vertex to the polygon
        newPoly->PushPoint(*polygon.begin());
    }

    void GridVectorization::FillAndBuildVectorField(char *grid, int const i, int const j, int const Lines, int const Columns, int searchValue, int fillValue, GridVectorField &fieldOut)
    {
        Vector vect;
        std::list<std::pair<int, int> > queue;
        if(i != -1 && j != -1) {
            queue.push_back(std::pair<int, int>(i, j));

            while(!queue.empty()) {
                int cX = queue.front().first;
                int cY = queue.front().second;
                grid[ cX * Columns + cY ] = fillValue;
                ///////////////////////////////////////////////////////////

                bool isEdge = false;
                for(int k = 0; k < 4; ++k) {
                    int ai = dirX[k] + cX;
                    int aj = dirY[k] + cY;

                    if(ai >= 0 && ai < Lines) {
                        if(aj >= 0 && aj < Columns) {
                            if( grid[ ai * Columns + aj ] != searchValue && grid[ ai * Columns + aj ] != fillValue)
                                isEdge = true;
                        }
                        else
                            isEdge = true;
                    }
                    else
                        isEdge = true;
                }

                if(isEdge) {

                    vect.xSource = cX;
                    vect.ySource = cY;

                    vect.xdir = 0;
                    vect.ydir = 1;
                    fieldOut.AddVector(cX, cY, vect);

                    vect.xdir = 1;
                    vect.ydir = 0;
                    //safe to do because the vector field has its own validation methods
                    fieldOut.AddVector(cX, cY + 1, vect);

                    //safe to do because the vector field has its own validation methods
                    vect.xdir = 0;
                    vect.ydir = -1;
                    fieldOut.AddVector(cX + 1, cY + 1, vect);

                    //safe to do because the vector field has its own validation methods
                    vect.xdir = -1;
                    vect.ydir = 0;
                    fieldOut.AddVector(cX + 1, cY, vect);

                }

                ///////////////////////////////////////////////////////////
                for(int k = 0; k < 4; ++k) {
                    int ai = dirX[k] + cX;
                    int aj = dirY[k] + cY;

                    if(ai >= 0 && ai < Lines)
                        if(aj >= 0 && aj < Columns)
                            if( grid[ ai * Columns + aj ] == searchValue ) {
                                grid[ ai * Columns + aj ] = fillValue;
                                queue.push_back(std::pair<int, int>(ai, aj));
                            }
                }
                queue.pop_front();
            }
        }
    }

    void GridVectorization::FillAndClearVectorField(char *grid, int const i, int const j, int const Lines, int const Columns, int searchValue, int fillValue, GridVectorField &fieldOut)
    {
        std::list<std::pair<int, int> > queue;
        if(i != -1 && j != -1) {
            queue.push_back(std::pair<int, int>(i, j));

            while(!queue.empty()) {
                int cX = queue.front().first;
                int cY = queue.front().second;

                grid[ cX * Columns + cY ] = fillValue;
                ///////////////////////////////////////////////////////////

                fieldOut.ClearVector(cX, cY);
                fieldOut.ClearVector(cX, cY + 1);
                fieldOut.ClearVector(cX + 1, cY + 1);
                fieldOut.ClearVector(cX + 1, cY);

                ///////////////////////////////////////////////////////////
                for(int k = 0; k < 4; ++k) {
                    int ai = dirX[k] + cX;
                    int aj = dirY[k] + cY;

                    if(ai >= 0 && ai < Lines)
                        if(aj >= 0 && aj < Columns)
                            if( grid[ ai * Columns + aj ] == searchValue ) {
                                queue.push_back(std::pair<int, int>(ai, aj));
                                grid[ ai * Columns + aj ] = fillValue;
                            }
                }
                queue.pop_front();
            }
        }
    }

    void GridVectorization::Fill( char *grid, int const i, int const j, int const aabbWidth, int const aabbHeight, int const Lines, int const Columns, int searchValue, int fillValue )
    {
        std::list<std::pair<int, int> > queue;
        int minLines, maxLines;
        int minColumns, maxColumns;

        if(searchValue == specialGridFlag) {
            //reserved
            printf("Search value is reserved!\n");
            grid[ i * Columns + j ] = fillValue;
            return;
        }

        minLines = maxLines = i;
        minColumns = maxColumns = j;

        bool stopColumns = false, stopLines = false;

        if(i != -1 && j != -1) {
            queue.push_back(std::pair<int, int>(i, j));

            while(!queue.empty()) {
                int cX = queue.front().first;
                int cY = queue.front().second;

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

                if(!stopLines) {
                    if(cX < minLines)
                        minLines = cX;

                    if(cX > maxLines)
                        maxLines = cX;
                }

                if(!stopColumns) {

                    if(cY < minColumns)
                        minColumns = cY;

                    if(cY > maxColumns)
                        maxColumns = cY;
                }

                if(maxColumns - minColumns + 1 >= aabbWidth)
                    stopColumns = true;

                if(maxLines - minLines + 1 >= aabbHeight)
                    stopLines = true;

                grid[ cX * Columns + cY ] = fillValue;

                if(stopColumns || stopLines) {
                    if(cX < minLines || cX > maxLines)
                        grid[ cX * Columns + cY ] = searchValue;

                    if(cY < minColumns || cY > maxColumns)
                        grid[ cX * Columns + cY ] = searchValue;
                }

                ///////////////////////////////////////////////////////////
                for(int k = 0; k < 4; ++k) {
                    int ai = dirX[k] + cX;
                    int aj = dirY[k] + cY;

                    if(stopLines) {
                        if(ai >= minLines && ai <= maxLines)
                            if(stopColumns) {
                                if(aj >= minColumns && aj <= maxColumns && grid[ ai * Columns + aj ] == searchValue ) {
                                    queue.push_back(std::pair<int, int>(ai, aj));
                                    grid[ ai * Columns + aj ] = specialGridFlag;
                                }
                            }
                            else {
                                if(aj >= 0 && aj < Columns)
                                    if( grid[ ai * Columns + aj ] == searchValue ) {
                                        queue.push_back(std::pair<int, int>(ai, aj));
                                        grid[ ai * Columns + aj ] = specialGridFlag;
                                    }
                            }
                    }
                    else {
                        if(ai >= 0 && ai < Lines)
                            if(stopColumns) {
                                if(aj >= minColumns && aj <= maxColumns && grid[ ai * Columns + aj ]  ==  searchValue ) {
                                    queue.push_back(std::pair<int, int>(ai, aj));
                                    grid[ ai * Columns + aj ] = specialGridFlag;
                                }
                            }
                            else {
                                if(aj >= 0 && aj < Columns)
                                    if(grid[ ai * Columns + aj ]  ==  searchValue ) {
                                        queue.push_back(std::pair<int, int>(ai, aj));
                                        grid[ ai * Columns + aj ] = specialGridFlag;
                                    }
                            }
                    }
                }
                queue.pop_front();
            }
        }
    }

    bool GridVectorization::IsReachable( char *grid, int const Lines, int const Columns, int sourceX, int sourceY, int destX, int destY )
    {
        bool passable = false;

        if(sourceX < Lines && sourceX >= 0 && sourceY < Columns && sourceY >= 0)
            if(destX < Lines && destX >= 0 && destY < Columns && destY >= 0)
                passable = true;


        if(!passable) {
            return false;
        }

        char searchValue =  grid[ sourceX * Columns + sourceY ];
        char destValue = grid[ destX * Columns + destY ];


        if(destValue != searchValue) {
            return false;
        }

        else {

            bool validDir = false;

            // backslash orientation
            if( (destX == sourceX + 1 && destY == sourceY + 1) || (sourceX == destX + 1 && sourceY == destY + 1) ) {
                char upRight = grid[ sourceX * Columns + destY ];
                char downLeft = grid[ destX * Columns + sourceY ];

                if(upRight == searchValue || downLeft == searchValue)
                    validDir = true;
            }

            //slash orientation
            if ((destX == sourceX - 1 && destY == sourceY + 1) || (sourceX == destX - 1 && sourceY == destY + 1)) {

                char upLeft = grid[ destX * Columns + sourceY ];
                char downRight = grid[ sourceX * Columns + destY ];

                if(downRight == searchValue || upLeft == searchValue)
                    validDir = true;
            }

            if(sourceX == destX || sourceY == destY)
                validDir = true;

            if(sourceX == destX &&
                sourceY == destY)
                validDir = true;

            return validDir;
        }
    }

    void GridVectorization::BuildCwVectorField( char *grid, int const Lines, int const Columns, int searchValue, GridVectorField &fieldOut )
    {
        fieldOut.Reset(Lines + 1, Columns + 1);
        for(int i=0; i<Lines; ++i)
            for(int j=0; j<Columns; ++j) {
                if(grid[i * Columns + j] == searchValue) {

                    Vector vect;
                    vect.xSource = i;
                    vect.ySource = j;

                    vect.xdir = 0;
                    vect.ydir = 1;
                    fieldOut.AddVector(i, j, vect);

                    vect.xdir = 1;
                    vect.ydir = 0;
                    //safe to do because the vector field has its own validation methods
                    fieldOut.AddVector(i, j + 1, vect);

                    //safe to do because the vector field has its own validation methods
                    vect.xdir = 0;
                    vect.ydir = -1;
                    fieldOut.AddVector(i + 1, j + 1, vect);

                    //safe to do because the vector field has its own validation methods
                    vect.xdir = -1;
                    vect.ydir = 0;
                    fieldOut.AddVector(i + 1, j, vect);
                }
            }
    }

    void GridVectorization::BuildCcwVectorField( char *grid, int const Lines, int const Columns, int searchValue, GridVectorField &fieldOut )
    {
        //counter clockwise vector field
    }

    void Graph::SafeFree()
    {
        steps = 0;
        if(adj) {

            for(int i=0; i<GetVertexCount(); ++i)
                if(adj[i])
                    free(adj[i]);
            delete []adj;
            adj = 0;
        }

        if(edgelists) {
            invalid_edge_lists = false;
            delete []edgelists;
            edgelists = 0;
        }

        if(in) {
            delete []in;
            in = 0;
        }

        if(out) {
            delete []out;
            out = 0;
        }
    }

    void Graph::SetVertexCount( int count )
    {
        SafeFree();

        if(count <= 0) {
            m_vertexCount = 0;
            return;
        }

        adj = new short*[count];
        edgelists = new list<int>[count];
        in = new short[count];
        memset(in, 0x0, count * sizeof(short));
        out = new short[count];
        memset(out, 0x0, count * sizeof(short));


        for (int i=0; i<count; ++i) {
            adj[i] = (short *)malloc(count * sizeof(short));
            if(!adj[i]) {
                printf("Couldn't allocate memory for the graph!\n");
                exit(1);
                break;
            }
        }

        m_vertexCount = count;

        for(int i=0; i<m_vertexCount; ++i) {
            memset(adj[i], -1, m_vertexCount * sizeof(short));
        }
    }

    Graph::Graph()
    {
        adj = 0;
        in = 0;
        out = 0;
        edgelists = 0;
        steps = 0;
        SetVertexCount(0);
    }

    void Graph::SetWeight( short weight, int i, int j )
    {
        if(i >= m_vertexCount || j >= m_vertexCount || i < 0 || j < 0) {
            return;
        }

        if(weight >= 0 && *(adj[i] + j) < 0) {
            in[j] ++;
            out[i] ++;
            edgelists[i].push_back(j);
            //add edge
        }
        else if(weight < 0 && *(adj[i] + j) >= 0) {
            in[j] --;
            out[i] --;
            //remove edge
        }
        *(adj[i] + j) = weight;
    }

    short Graph::GetWeight( int i, int j ) const
    {
        if(i >= m_vertexCount || j >= m_vertexCount || i < 0 || j < 0) {
            return -1;
        }
        return *(adj[i] + j);
    }

    void Graph::TopologicalSortingVariantOne( std::vector<int> &out ) const
    {
        //O(m + n) steps
        if(GetVertexCount() == 0)
            return;

        Graph const &g = *this;
        std::vector<int> removed;

        int n = g.GetVertexCount();
        int count = n;

        for(int i=0; i<n; ++i) {
            removed.push_back(0);
        }

        short *in = new short[n];

        memcpy(in, g.in, n * sizeof(short));

        int steps = 0;
        while(count) {
            for(int i=0; i<n; ++i)
                if(!removed[i] && !in[i]) {
                    for(list<int>::const_iterator it = g.edgelists[i].begin(); it != g.edgelists[i].end(); ++it) {
                        in[*it]--;
                        steps++;
                    }
                    count--;
                    out.push_back(i);
                    removed[i] = 1;
                }
        }
        delete []in;
    }

    void Graph::GetMaximumWeightedPath( std::vector<int> &out )
    {
        // O(m + n)

        if(GetVertexCount() == 0)
            return;

        Graph const &g = *this;

        std::vector<int> sorted;
        std::vector<int> costs, prev;
        int last = -1;

        for(int i=0; i<g.GetVertexCount(); ++i) {
            costs.push_back(-1);
            prev.push_back(-1);
        }


        g.TopologicalSortingVariantOne(sorted);
        costs[sorted[0]] = 0;

        for(unsigned i=0; i<sorted.size(); ++i) {
            int element = sorted[i];
            for(list<int>::const_iterator it = g.edgelists[element].begin(); it != g.edgelists[element].end(); ++it) {
                if(costs[*it] < g.GetWeight(element, *it) + costs[element]) {
                    costs[*it] = g.GetWeight(element, *it) + costs[element];
                    prev[*it] = element;
                    last = *it;
                    ++steps;
                }
            }
        }

        last = g.GetVertexCount() - 1;

        for(int i = last; i != -1; i = prev[i]) {
            out.push_back(i);
        }
    }

    Point2D::Point2D()
    {
        x = 0.0;
        y = 0.0;
    }

    Point2D::Point2D( double x, double y )
    {
        this->x = x;
        this->y = y;
    }

    Point2D Point2D::operator-( const Point2D &other ) const
    {
        Point2D result;
        result.x = x - other.x;
        result.y = y - other.y;
        return result;
    }

    Line2D::Line2D( const Point2D &A, const Point2D &B )
    {
        this->A = A;
        this->B = B;
    }

    GridVectorField::GridVectorField( int lines, int columns )
    {
        grid = 0;
        Reset(lines, columns);
    }

    void GridVectorField::AddVector( int i, int j, Vector &vector )
    {
        if(i < lines && j < columns && i >= 0 && j >= 0) {
            BoundVectorListPtr list = grid[i * columns + j];
            if(!list) {
                list = new BoundVectorList();
                sparseLists.push_back(list);
                grid[i * columns + j] = list;
            }
            list->push_back(vector);
        }
    }

    BoundVectorListPtr GridVectorField::GetVectorList( int i, int j ) const
    {
        if(i < lines && j < columns && i >= 0 && j >= 0) {
            BoundVectorListPtr list = grid[i * columns + j];
            return list;
        }
        return 0;
    }

    void GridVectorField::Clear()
    {
        if(grid) {
            delete []grid;
            for(std::list<BoundVectorListPtr>::iterator it = sparseLists.begin(); it != sparseLists.end(); ++it) {
                delete (*it);
            }
            sparseLists.clear();
        }
    }

    void GridVectorField::ClearVector( int i, int j )
    {
        if(i < lines && j < columns && i >= 0 && j >= 0) {
            if(grid[i * columns + j])
                grid[i * columns + j]->clear();
        }
    }
}

Can you give me a test similar to the fifth test. Just i dont know where i have endless cycle? Sorry for my english.

What it is about?

I think, in some tastes circles are not "ideal" (i. e. absolutely symmetric with respect to both axes and its' centre)

Can somebody tell me the possible reason of this WA?
Or at least what figure is in that test?

I would be very thankful!

submit_id = 4065802
the following Assert is failed: "is there at least one '1' in the matrix?"

I guess it's a circle, but what is special about it? Is it very large or small, or something like that?

----

Not needed now.

Edited by author 07.12.2011 20:16

What is the test32?
What dimensionality of the matrix?
Is it square?

I`m confused... I don`t understand this test

Hello, I don't understand description of this task. I am interesting in borders of possible "image". Is the side of square can be i.e. 48x48px (popugaev):), but canvas of image i.e. 200x200? and square can be anywhere on that canvas or it always in the center? It's very important term for solution. Ofcourse, I understand that shapes can be rotated at different angles.

It's seems to be some strange square with more than 4 corners.

I've made a mistake in input W and H order, but get Accepted...

Does anyone know this test? Or at least can you say what figure is it?
My prog solves a problem even with ellipses and rectangles, because I don't know whether it should or not.

Edited by author 28.09.2010 01:34

I had WA 12, now I have WA 17. I still need your help!

Edited by author 28.09.2010 22:23

Try to find minimal and maximal distance between figure's center and border, and think about possible shapes.

Note to those who tries to solve it: sides of rectangles do not have to be parrallel to axes, and any of three shapes do not have to be aligned in any way on the grid.
Tip: you can get advantage from the fact shape cannot be very small. Possible solution is not evident, but logically clear and short.

Hello. My solution gets WA on then 7'th test. I can't realize, why it does.

my algorithm:

  find the described rectangle (x1,y1,x2,y2)
  if abs((x2-x1)-(y2-y1))>3 then it is triangle;exit;
  if abs((x2-x1)-(y2-y1))=0 then check if is rectangle; if it's so, then exit;

  here I have a figure (triangle or circle) that is described with "nearly" square. I allow that the circle can be described not with a square (because of roundings). I calculate the area of the figure. Then:

  if area>5/8*sqr(((x2-x1+1)+(y2-y1+1))/2) then
    it is circle
  else
    it is triangle

the final decision is based on this:
  For example, triangle in described with a square with side = A. Then it's area ranges from 0 (not including) to sqr(A)/2 (including). The circle with diameter=A have area that is nearly equal to PI/4*sqr(A). The number 5/8 lies between 1/2 and PI/4.

why does my solution not get AC?

Edited by author 12.04.2008 21:08