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? You just calculate frequencies of appearing black cells for every row and column. This requires only ~10Kb of memory, and at the same time allows to recognize the figure Thank you for your answer. But I still don't know how to use frequencies for recognition figures... Just think how density functions of projection of every of these figures look like. Circle recognition is easy even by one projection. For some bad cases of squares and triangles you need both projections. wow! beautifull idea :) My solution use symmetric of figures. In fact, better solution than Sergei said is possible. I think if done in assembly under MS-DOS, solution could use less than half of kilobyte of memory. I save only 8 points which enough for solution 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. I think, in some tastes circles are not "ideal" (i. e. absolutely symmetric with respect to both axes and its' centre) +1. The problem is elegant, but some tests are messy. Test 2: "circle 50x56" is oval. what is test 8? Edited by author 25.10.2013 07:44 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?" Test 37 is correct. Read the problem statement: the first number in the input is the width, not the height. Thank you. Now that both solutions have AC =) P.S. It was so unexpected... Two different solutions, both pass 36 tests, and the only bug is "w h". 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 I have the same problem =( 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. Apply the GOOD JOB for College ACMers to Make Large Money and Become a Millionaire Hello, We need large no. of dedicated and hard working ACMers. The payment is good so we need ACMers to be efficient. All you have to do to get the job is to sign up at our websites. The link of our websites are given below. http://www.PaisaLive.com/register.asp?3556638-4847933 After the registration, a confirmation email will be sent to your specified email address. Please click on the link inside the confirmation email to activate your account and recieve ACM work instantly. For any other queries you can mail the administrator. Miss Juliet Admin paisalive.com Thank you, it was the best answer ever! It's seems to be some strange square with more than 4 corners. Square in 7th test has 4 corners. then, you can see my last AC solution and design some test for it to fail ) It may be isosceles rectangular triangle as half of that square in 7th test. If you can, please mail me that square to aterlux (at) mail (dot) ru. Thanks a lot 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 Somebody! What figure is it?! I tried to count an amount of corners, values of sides, radiuses and areas, curvature (кривизна) of line between two corners... All methods work with simple examples but do not in the 17-th test. 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. Yeah, really interesting problem. 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 |
|