#include #include #include #define NOTHING 50000 #define NO_NEIGHBOR -1 using namespace std; struct vertex { int x; int y; int neighbor1X; int neighbor1Y; char neighbor1Direction; int neighbor1Index; int neighbor2Index; char neighbor2Direction; char nextDirection; bool operator==(const vertex& ver) { return (x == ver.x) && (y == ver.y); } }; char opposite(char dir) { if (dir == 'N') { return 'S'; } else if (dir == 'S') { return 'N'; }else if (dir == 'E') { return 'W'; }else { return 'E'; } } int main() { int count; vector vertices; for (;;) { vertices.clear(); cin >> count; if (count == 0) {break;} int x, y; vertex minXMinY, minXMaxY, maxXMinY, maxXMaxY, minYMinX, minYMaxX, maxYMinX, maxYMaxX; for (int i=0; i< count; i++) { cin >> x; cin >> y; vertex temp; temp.x = x; temp.y = y; temp.neighbor1X = NOTHING; temp.neighbor1Y = NOTHING; temp.neighbor1Direction = 'X'; temp.neighbor1Index = NO_NEIGHBOR; temp.neighbor2Index = NO_NEIGHBOR; temp.neighbor2Direction = 'X'; temp.nextDirection = 'X'; if (i == 0) { minXMinY = temp; minXMaxY = temp; maxXMinY = temp; maxXMaxY = temp; minYMinX = temp; minYMaxX = temp; maxYMinX = temp; maxYMaxX = temp; } if ((x= minXMaxY.y))) { minXMaxY = temp; } if ((x > maxXMinY.x) || ((x >= maxXMinY.x) && (y <= maxXMinY.y))) { maxXMinY = temp; } if ((x > maxXMaxY.x) || ((x >= maxXMaxY.x) && (y >= maxXMaxY.y))) { maxXMaxY = temp; } if ((y < minYMinX.y) || ((x <= minYMinX.x) && (y <= minYMinX.y))) { minYMinX = temp; } if ((y < minYMaxX.y) || ((x <= minYMaxX.x) && (y >= minYMaxX.y))) { minYMaxX = temp; } if ((y > maxYMinX.y) || ((x >= maxYMinX.x) && (y <= maxYMinX.y))) { maxYMinX = temp; } if ((y > maxYMaxX.y) || ((x >= maxYMaxX.x) && (y >= maxYMaxX.y))) { maxYMaxX = temp; } vertices.push_back(temp); }//konec nacitani // prvni iterace se dvema hranami u kazdeho z 8 specialnich for (int i=0; i minXMinY.y) &&(minXMinY.neighbor1Index!=-1 || (abs(minXMinY.y - vertices[i].y) < abs(minXMinY.y - vertices[minXMinY.neighbor1Index].y) ))) { minXMinY.neighbor1Index=i; minXMinY.neighbor1Direction = 'N'; } //stejna rada, sloupec vlevo if ((vertices[i].y == minXMinY.y) && (vertices[i].x > minXMinY.x) && (minXMinY.neighbor2Index!=-1 ||(abs(minXMinY.x - vertices[i].x) < abs(minXMinY.x - vertices[minXMinY.neighbor2Index].x) ))) { minXMinY.neighbor2Index=i; minXMinY.neighbor2Direction = 'E'; } //MINXMAXY // stejny sloupec, pod nami if ((vertices[i].x == minXMaxY.x) && (vertices[i].y < minXMaxY.y) &&(minXMaxY.neighbor1Index!=-1 || (abs(minXMaxY.y - vertices[i].y) < abs(minXMaxY.y - vertices[minXMaxY.neighbor1Index].y) ))) { minXMaxY.neighbor1Index=i; minXMaxY.neighbor1Direction = 'S'; } //stejna rada, sloupec vlevo if ((vertices[i].y == minXMaxY.y) && (vertices[i].x > minXMaxY.x) && (minXMaxY.neighbor2Index!=-1 ||(abs(minXMaxY.x - vertices[i].x) < abs(minXMaxY.x - vertices[minXMaxY.neighbor2Index].x) ))) { minXMaxY.neighbor2Index=i; minXMaxY.neighbor2Direction = 'E'; } // stejny sloupec, nad nami //MAXXMINY if ((vertices[i].x == maxXMinY.x) && (vertices[i].y > maxXMinY.y) && (maxXMinY.neighbor1Index!=-1 || (abs(maxXMinY.y - vertices[i].y) < abs(maxXMinY.y - vertices[maxXMinY.neighbor1Index].y) ))) { maxXMinY.neighbor1Index=i; maxXMinY.neighbor1Direction = 'N'; } //stejna rada, sloupec vpravo if ((vertices[i].y == maxXMinY.y) && (vertices[i].x < maxXMinY.x) && (maxXMinY.neighbor2Index!=-1 ||(abs(maxXMinY.x - vertices[i].x) < abs(maxXMinY.x - vertices[maxXMinY.neighbor2Index].x) ) )){ maxXMinY.neighbor2Index=i; maxXMinY.neighbor2Direction = 'W'; } //MAXXMAXY // stejny sloupec, pod nami if ((vertices[i].x == maxXMaxY.x) && (vertices[i].y < maxXMaxY.y) && (maxXMaxY.neighbor1Index!=-1 || (abs(maxXMaxY.y - vertices[i].y) < abs(maxXMaxY.y - vertices[maxXMaxY.neighbor1Index].y) ))) { maxXMaxY.neighbor1Index=i; maxXMaxY.neighbor1Direction = 'S'; } //stejna rada, sloupec vpravo if ((vertices[i].y == maxXMaxY.y) && (vertices[i].x < maxXMaxY.x) && (maxXMaxY.neighbor2Index!=-1 ||(abs(maxXMaxY.x - vertices[i].x) < abs(maxXMaxY.x - vertices[maxXMaxY.neighbor2Index].x) )) ){ maxXMaxY.neighbor2Index=i; maxXMaxY.neighbor2Direction = 'W'; } //MINXMINY // stejny sloupec, nad nami if ((vertices[i].x == minYMinX.x) && (vertices[i].y > minYMinX.y) && (minYMinX.neighbor1Index!=-1 || (abs(minYMinX.y - vertices[i].y) < abs(minYMinX.y - vertices[minYMinX.neighbor1Index].y) )) ){ minYMinX.neighbor1Index=i; minYMinX.neighbor1Direction = 'N'; } //stejna rada, sloupec vlevo if ((vertices[i].y == minYMinX.y) && (vertices[i].x > minYMinX.x) && (minYMinX.neighbor2Index!=-1 ||(abs(minYMinX.x - vertices[i].x) < abs(minYMinX.x - vertices[minYMinX.neighbor2Index].x) )) ){ minYMinX.neighbor2Index=i; minYMinX.neighbor1Direction = 'E'; } //MINXMAXY // stejny sloupec, pod nami if ((vertices[i].x == minYMaxX.x) && (vertices[i].y < minYMaxX.y) && (minYMaxX.neighbor1Index!=-1 || (abs(minYMaxX.y - vertices[i].y) < abs(minYMaxX.y - vertices[minYMaxX.neighbor1Index].y) ) )){ minYMaxX.neighbor1Index=i; minYMaxX.neighbor1Direction = 'S'; } //stejna rada, sloupec vlevo if ((vertices[i].y == minYMaxX.y) && (vertices[i].x > minYMaxX.x) && (minYMaxX.neighbor2Index!=-1 ||(abs(minYMaxX.x - vertices[i].x) < abs(minYMaxX.x - vertices[minYMaxX.neighbor2Index].x) ))){ minYMaxX.neighbor2Index=i; minYMaxX.neighbor2Direction = 'E'; } // stejny sloupec, nad nami //MAXXMINY if ((vertices[i].x == maxYMinX.x) && (vertices[i].y > maxYMinX.y) && (maxYMinX.neighbor1Index!=-1 || (abs(maxYMinX.y - vertices[i].y) < abs(maxYMinX.y - vertices[maxYMinX.neighbor1Index].y) ))) { maxYMinX.neighbor1Index=i; maxYMinX.neighbor1Direction = 'N'; } //stejna rada, sloupec vpravo if ((vertices[i].y == maxYMinX.y) && (vertices[i].x < maxYMinX.x) && (maxYMinX.neighbor2Index!=-1 ||(abs(maxYMinX.x - vertices[i].x) < abs(maxYMinX.x - vertices[maxYMinX.neighbor2Index].x) )) ){ maxYMinX.neighbor2Index=i; maxYMinX.neighbor2Direction = 'W'; } //MAXXMAXY // stejny sloupec, pod nami if ((vertices[i].x == maxYMaxX.x) && (vertices[i].y < maxYMaxX.y) && (maxYMaxX.neighbor1Index!=-1 || (abs(maxYMaxX.y - vertices[i].y) < abs(maxYMaxX.y - vertices[maxYMaxX.neighbor1Index].y) ))) { maxYMaxX.neighbor1Index=i; maxYMaxX.neighbor1Direction = 'S'; } //stejna rada, sloupec vpravo if ((vertices[i].y == maxYMaxX.y) && (vertices[i].x < maxYMaxX.x) && (maxYMaxX.neighbor2Index!=-1 || (abs(maxYMaxX.x - vertices[i].x) < abs(maxYMaxX.x - vertices[maxYMaxX.neighbor2Index].x) ))) { maxYMaxX.neighbor2Index=i; maxYMaxX.neighbor1Direction = 'W'; } }// cyklus dokud nejsou vsechny hrany, pridavani po jedne // neighborum priradit index maxXmaxY... //cyklus - probirani postupne nejlevejsich atd pridavani jedne hrany for (int i=0; i= minXMaxY.y))) ){ minXMaxY = vertices[i]; allHaveNeighbors = false; } if ((vertices[i].neighbor1Index==-1 || vertices[i].neighbor2Index==-1) && ((x > maxXMinY.x) || ((x >= maxXMinY.x) && (y <= maxXMinY.y)))) { maxXMinY = vertices[i]; allHaveNeighbors = false; } if ((vertices[i].neighbor1Index==-1 || vertices[i].neighbor2Index==-1) && ((x > maxXMaxY.x) || ((x >= maxXMaxY.x) && (y >= maxXMaxY.y)))) { maxXMaxY = vertices[i]; allHaveNeighbors = false; } if ((vertices[i].neighbor1Index==-1 || vertices[i].neighbor2Index==-1) && ((y < minYMinX.y) || ((x <= minYMinX.x) && (y <= minYMinX.y)))) { minYMinX = vertices[i]; allHaveNeighbors = false; } if ((vertices[i].neighbor1Index==-1 || vertices[i].neighbor2Index==-1) && ((y < minYMaxX.y) || ((x <= minYMaxX.x) && (y >= minYMaxX.y)))) { minYMaxX = vertices[i]; allHaveNeighbors = false; } if ((vertices[i].neighbor1Index==-1 || vertices[i].neighbor2Index==-1) && ((y > maxYMinX.y) || ((x >= maxYMinX.x) && (y <= maxYMinX.y)))) { maxYMinX = vertices[i]; allHaveNeighbors = false; } if ((vertices[i].neighbor1Index==-1 || vertices[i].neighbor2Index==-1) && ((y > maxYMaxX.y) || ((x >= maxYMaxX.x) && (y >= maxYMaxX.y)))) { maxYMaxX = vertices[i]; allHaveNeighbors = false; } //MINXMINY // stejny sloupec, nad nami if (vertices[i].neighbor1Index==-1 &&(vertices[i].x == minXMinY.x) && (vertices[i].y > minXMinY.y) &&(minXMinY.neighbor1Index!=-1 || (abs(minXMinY.y - vertices[i].y) < abs(minXMinY.y - vertices[minXMinY.neighbor1Index].y) ))) { minXMinY.neighbor1Index=i; minXMinY.neighbor1Direction = 'N'; } //stejna rada, sloupec vlevo if (vertices[i].neighbor2Index==-1 &&(vertices[i].y == minXMinY.y) && (vertices[i].x > minXMinY.x) && (minXMinY.neighbor2Index!=-1 ||(abs(minXMinY.x - vertices[i].x) < abs(minXMinY.x - vertices[minXMinY.neighbor2Index].x) ))) { minXMinY.neighbor2Index=i; minXMinY.neighbor2Direction = 'E'; } //MINXMAXY // stejny sloupec, pod nami if (vertices[i].neighbor1Index==-1 &&(vertices[i].x == minXMaxY.x) && (vertices[i].y < minXMaxY.y) &&(minXMaxY.neighbor1Index!=-1 || (abs(minXMaxY.y - vertices[i].y) < abs(minXMaxY.y - vertices[minXMaxY.neighbor1Index].y) ))) { minXMaxY.neighbor1Index=i; minXMaxY.neighbor1Direction = 'S'; } //stejna rada, sloupec vlevo if (vertices[i].neighbor2Index==-1 &&(vertices[i].y == minXMaxY.y) && (vertices[i].x > minXMaxY.x) && (minXMaxY.neighbor2Index!=-1 ||(abs(minXMaxY.x - vertices[i].x) < abs(minXMaxY.x - vertices[minXMaxY.neighbor2Index].x) ))) { minXMaxY.neighbor2Index=i; minXMaxY.neighbor2Direction = 'E'; } // stejny sloupec, nad nami //MAXXMINY if (vertices[i].neighbor1Index==-1 &&(vertices[i].x == maxXMinY.x) && (vertices[i].y > maxXMinY.y) && (maxXMinY.neighbor1Index!=-1 || (abs(maxXMinY.y - vertices[i].y) < abs(maxXMinY.y - vertices[maxXMinY.neighbor1Index].y) ))) { maxXMinY.neighbor1Index=i; maxXMinY.neighbor1Direction = 'N'; } //stejna rada, sloupec vpravo if (vertices[i].neighbor2Index==-1 &&(vertices[i].y == maxXMinY.y) && (vertices[i].x < maxXMinY.x) && (maxXMinY.neighbor2Index!=-1 ||(abs(maxXMinY.x - vertices[i].x) < abs(maxXMinY.x - vertices[maxXMinY.neighbor2Index].x) ) )){ maxXMinY.neighbor2Index=i; maxXMinY.neighbor2Direction = 'W'; } //MAXXMAXY // stejny sloupec, pod nami if (vertices[i].neighbor1Index==-1 &&(vertices[i].x == maxXMaxY.x) && (vertices[i].y < maxXMaxY.y) && (maxXMaxY.neighbor1Index!=-1 || (abs(maxXMaxY.y - vertices[i].y) < abs(maxXMaxY.y - vertices[maxXMaxY.neighbor1Index].y) ))) { maxXMaxY.neighbor1Index=i; maxXMaxY.neighbor1Direction = 'S'; } //stejna rada, sloupec vpravo if (vertices[i].neighbor2Index==-1 &&(vertices[i].y == maxXMaxY.y) && (vertices[i].x < maxXMaxY.x) && (maxXMaxY.neighbor2Index!=-1 ||(abs(maxXMaxY.x - vertices[i].x) < abs(maxXMaxY.x - vertices[maxXMaxY.neighbor2Index].x) )) ){ maxXMaxY.neighbor2Index=i; maxXMaxY.neighbor2Direction = 'W'; } //MINXMINY // stejny sloupec, nad nami if (vertices[i].neighbor1Index==-1 &&(vertices[i].x == minYMinX.x) && (vertices[i].y > minYMinX.y) && (minYMinX.neighbor1Index!=-1 || (abs(minYMinX.y - vertices[i].y) < abs(minYMinX.y - vertices[minYMinX.neighbor1Index].y) )) ){ minYMinX.neighbor1Index=i; minYMinX.neighbor1Direction = 'N'; } //stejna rada, sloupec vlevo if (vertices[i].neighbor2Index==-1 &&(vertices[i].y == minYMinX.y) && (vertices[i].x > minYMinX.x) && (minYMinX.neighbor2Index!=-1 ||(abs(minYMinX.x - vertices[i].x) < abs(minYMinX.x - vertices[minYMinX.neighbor2Index].x) )) ){ minYMinX.neighbor2Index=i; minYMinX.neighbor1Direction = 'E'; } //MINXMAXY // stejny sloupec, pod nami if (vertices[i].neighbor1Index==-1 &&(vertices[i].x == minYMaxX.x) && (vertices[i].y < minYMaxX.y) && (minYMaxX.neighbor1Index!=-1 || (abs(minYMaxX.y - vertices[i].y) < abs(minYMaxX.y - vertices[minYMaxX.neighbor1Index].y) ) )){ minYMaxX.neighbor1Index=i; minYMaxX.neighbor1Direction = 'S'; } //stejna rada, sloupec vlevo if (vertices[i].neighbor2Index==-1 &&(vertices[i].y == minYMaxX.y) && (vertices[i].x > minYMaxX.x) && (minYMaxX.neighbor2Index!=-1 ||(abs(minYMaxX.x - vertices[i].x) < abs(minYMaxX.x - vertices[minYMaxX.neighbor2Index].x) ))){ minYMaxX.neighbor2Index=i; minYMaxX.neighbor2Direction = 'E'; } // stejny sloupec, nad nami //MAXXMINY if (vertices[i].neighbor1Index==-1 &&(vertices[i].x == maxYMinX.x) && (vertices[i].y > maxYMinX.y) && (maxYMinX.neighbor1Index!=-1 || (abs(maxYMinX.y - vertices[i].y) < abs(maxYMinX.y - vertices[maxYMinX.neighbor1Index].y) ))) { maxYMinX.neighbor1Index=i; maxYMinX.neighbor1Direction = 'N'; } //stejna rada, sloupec vpravo if (vertices[i].neighbor2Index==-1 &&(vertices[i].y == maxYMinX.y) && (vertices[i].x < maxYMinX.x) && (maxYMinX.neighbor2Index!=-1 ||(abs(maxYMinX.x - vertices[i].x) < abs(maxYMinX.x - vertices[maxYMinX.neighbor2Index].x) )) ){ maxYMinX.neighbor2Index=i; maxYMinX.neighbor2Direction = 'W'; } //MAXXMAXY // stejny sloupec, pod nami if (vertices[i].neighbor1Index==-1 &&(vertices[i].x == maxYMaxX.x) && (vertices[i].y < maxYMaxX.y) && (maxYMaxX.neighbor1Index!=-1 || (abs(maxYMaxX.y - vertices[i].y) < abs(maxYMaxX.y - vertices[maxYMaxX.neighbor1Index].y) ))) { maxYMaxX.neighbor1Index=i; maxYMaxX.neighbor1Direction = 'S'; } //stejna rada, sloupec vpravo if (vertices[i].neighbor2Index==-1 &&(vertices[i].y == maxYMaxX.y) && (vertices[i].x < maxYMaxX.x) && (maxYMaxX.neighbor2Index!=-1 || (abs(maxYMaxX.x - vertices[i].x) < abs(maxYMaxX.x - vertices[maxYMaxX.neighbor2Index].x) ))) { maxYMaxX.neighbor2Index=i; maxYMaxX.neighbor1Direction = 'W'; } }// cyklus dokud nejsou vsechny hrany, pridavani po jedne } int currentVertexIndex = 0; int nextVertexIndex = 0; for (;;) { if ((vertices[currentVertexIndex].neighbor1Direction == 'N') && (vertices[currentVertexIndex].neighbor2Direction == 'E')) { nextVertexIndex = vertices[currentVertexIndex].neighbor1Index; cout << 'N'; } if ((vertices[currentVertexIndex].neighbor1Direction == 'S') && (vertices[currentVertexIndex].neighbor2Direction == 'W')) { nextVertexIndex = vertices[currentVertexIndex].neighbor1Index; cout << 'S'; } if ((vertices[currentVertexIndex].neighbor1Direction == 'N') && (vertices[currentVertexIndex].neighbor2Direction == 'W')) { nextVertexIndex = vertices[currentVertexIndex].neighbor2Index; cout << 'W'; } if ((vertices[currentVertexIndex].neighbor1Direction == 'S') && (vertices[currentVertexIndex].neighbor2Direction == 'E')) { nextVertexIndex = vertices[currentVertexIndex].neighbor2Index; cout << 'E'; } currentVertexIndex = nextVertexIndex; if (nextVertexIndex == 0) break; } cout << endl; }//konec uplny return 0; }