#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 findPath(const map& ext, bool first) { size_t path = 0; 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; size_t base = 0; 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()}}); base += abs(*set.begin() - *--set.end()); } const auto p1 = findPath(ext, true); const auto p2 = findPath(ext, false); std::cout << base + min(p1, p2) << std::endl; }