#include #include #include #include using namespace std; using Point = std::pair; using Extreme = std::pair; int readint() { int res; std::cin >> res; return res; } /* int findShortest(const std::set& nodes, const std::map, int>& edges) { std::queue q; std::set v; auto nodeI = nodes.begin(); int westernmostX = nodeI->first; q.push(*nodeI); v.insert(*nodeI); while((++nodeI)->first == westernmostX) { q.push(*nodeI); v.insert(*nodeI); } while(!q.empty()) { } }*/ /*for(const auto& node : nodes) { int dist = abs(node.first - n.first) + abs(node.second - n.second); if(n.first > node.first) edges.insert({{n, node}, dist}); else edges.insert({{node, n}, dist}); } nodes.insert(n);*/ size_t diff(pair x) { return abs(x.first - x.second); } size_t findPath(const map& ext) { size_t path = (size_t) -1; const auto beg = ext.begin() -> second; const size_t sd = diff(beg); const size_t sl = ext.begin() -> first; auto q = queue>>({{sl, {beg.first, sd}}, {sl, {beg.second, sd}}}); while(!q.empty()) { const auto item = q.front(); q.pop(); if (item.first == (--ext.end()) -> first) { path = path < item.second.second ? path : item.second.second; continue; } auto next = (++ext.find(item.first)); auto nextLevel = next -> first; auto d = item.second.second + diff(next -> second); q.push({nextLevel, {next -> second.second, d + abs(item.first - nextLevel) + abs(next -> second.first - item.second.first)}}); q.push({nextLevel, {next -> second.first, d + abs(item.first - nextLevel) + abs(next -> second.second - item.second.first)}}); } /*for (auto level = ext.begin(); level != --ext.end(); ++level) { auto next = level; ++next; if (first) { path += abs(level -> second.first - next -> second.first); } else { path += abs(level -> second.second - next -> second.second); } path += next -> first - level -> first; first = !first; }*/ return path; } int main() { int n = readint(); std::map> map; for(int i = 0; i < n; i++) { auto x = readint(); auto y = readint(); auto find = map.find(x); if (find == map.end()) map.insert({x, set({y})}); else (*find).second.insert(y); } std::map ext; for (auto level = map.begin(); level != map.end(); ++level) { const auto key = level -> first; const auto set = level -> second; ext.insert({key, {*set.begin(), *--set.end()}}); } /*const auto p1 = findPath(ext, true); const auto p2 = findPath(ext, false);*/ std::cout << findPath(ext) << std::endl; }