#include #include #include #include #include struct Vertex; struct Edge{ Vertex * endVertex; long long cost; }; // directed graph struct Vertex { bool discovered = false; std::vector neighs = {}; }; struct Coord { int x, y; bool operator < (const Coord & other) const { if(this->x != other.x) return x < other.x; return y < other.y; } }; struct CoordAndDist{ Coord c; long long dist; int index; bool operator < (const CoordAndDist & other) const{ return this->dist > other.dist; } }; bool contains(std::map & m, int key) { return m.find(key) != m.end(); } std::set foundCoordinates; std::priority_queue queue; std::map greatestCoordForGivenX; std::map smallestCoordForGivenX; long long distBetween(Coord prev, int x, bool smallest) { long long res = 0; res += abs(x - prev.x); Coord finish, other; finish = smallestCoordForGivenX[x]; other = greatestCoordForGivenX[x]; if(!smallest) std::swap(finish, other); res += abs(prev.y - other.y); res += abs(other.y - finish.y); return res; } void enqueue(CoordAndDist cd) { if(foundCoordinates.find(cd.c) != foundCoordinates.end()) return; foundCoordinates.insert(cd.c); queue.push(cd); } int main() { int n; long long result = -1; std::cin >> n; int x, y; for(int i = 0; i < n; i++) { std::cin >> x >> y; Coord c = {x, y}; if(!contains(greatestCoordForGivenX, x)) { greatestCoordForGivenX[x] = c; smallestCoordForGivenX[x] = c; } else { if(greatestCoordForGivenX[x].y < y) greatestCoordForGivenX[x] = c; if(smallestCoordForGivenX[x].y > y) smallestCoordForGivenX[x] = c; } } std::vector keyCoords; for(auto & it : greatestCoordForGivenX) keyCoords.push_back(it.first); int firstX = keyCoords[0]; long long firstDist = abs(greatestCoordForGivenX[firstX].y - smallestCoordForGivenX[firstX].y); enqueue({greatestCoordForGivenX[firstX], firstDist, 0}); enqueue({smallestCoordForGivenX[firstX], firstDist, 0}); while(!queue.empty()) { CoordAndDist cd = queue.top(); queue.pop(); if (cd.index == keyCoords.size() - 1) { result = cd.dist; // std::cout << ("got here"); break; } x = keyCoords[cd.index + 1]; long long smallDist = distBetween(cd.c, x, true) + cd.dist; long long greatDist = distBetween(cd.c, x, false) + cd.dist; enqueue({smallestCoordForGivenX[x], smallDist, cd.index+1}); enqueue({greatestCoordForGivenX[x], greatDist, cd.index+1}); } std::cout << result << std::endl; return 0; }