ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1378. Artificial Intelligence

Where is the mistake, WA 4
Posted by Outermeasure 24 Dec 2014 00:23
#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();
        }
    }
}