#include #include #include #include using namespace std; int recFindPath(int startY, size_t layer, const vector>> & layeredCoords){ int layerDistance = 0; if(layeredCoords[layer].size() == 1) layerDistance = 0; else { layerDistance = abs(layeredCoords[layer][0].second - layeredCoords[layer][layeredCoords[layer].size()-1].second); } if(layer == layeredCoords.size()-1) return layerDistance; //---------konec-pocitani-vrstvy-------------- int currY; if(startY == layeredCoords[layer][0].second){ currY = layeredCoords[layer][layeredCoords[layer].size()-1].second; } else { currY = layeredCoords[layer][0].second; } int currX = layeredCoords[layer][0].first; int len = 0; int xDiif = layeredCoords[layer+1][0].first - currX; len += xDiif; int nextYTop = layeredCoords[layer+1][0].second; int nextYBot = layeredCoords[layer+1][layeredCoords[layer+1].size()-1].second; int lenTop = abs(currY - nextYTop); int lenBot = abs(currY - nextYBot); if(nextYBot == nextYTop){ len += recFindPath(nextYBot, layer+1, layeredCoords); len += lenTop; return layerDistance+len; } else { int len1 = recFindPath(nextYBot, layer+1, layeredCoords); int len2 = recFindPath(nextYTop, layer+1, layeredCoords); if(len1 < len2){ len += len1; len += lenBot; } else { len += len2; len += lenTop; } return layerDistance+len; } } int main (){ int numOfPoints; cin >> numOfPoints; vector> coords(numOfPoints); for (int i = 0; i < numOfPoints; ++i) { int x,y; cin >> x >> y; coords[i] = {x,y}; } std::sort(coords.begin(), coords.end(), [](const pair &a, const pair &b){ if(a.first == b.first) return a.second < b.second; return a.first < b.first; }); vector>> layeredCoords; for (size_t i = 0; i < coords.size(); ) { vector> cLayer; int currX = coords[i].first; while((coords[i].first == currX) && (i < coords.size())){ cLayer.push_back(coords[i]); ++i; } layeredCoords.push_back(cLayer); } int len = 0; if(layeredCoords[0].size() == 1) { len = recFindPath(layeredCoords[0][0].second, 0, layeredCoords); } else { int len1 = recFindPath(layeredCoords[0][0].second, 0, layeredCoords); int len2 = recFindPath(layeredCoords[0][layeredCoords[0].size()-1].second, 0, layeredCoords); if(len1 < len2) len = len1; else len = len2; } cout << len << endl; return 0; }