atE6TY - Online C++0x Compiler & Debugging Tool

#include <bits/stdc++.h> // NeOWami
using namespace std;

#define NeOWami signed
#define ft first
#define sc second
#define int long long
using pii = pair<int, int>;
template<class T> using heapmin = priority_queue<T, vector<T>, greater<T>>;
const int N = 1e6 + 5;
const int inf = 1e18;
int n, id[N], dist[N], par[N];
pii a[N], b[N];
vector<pii> G[N];
bool ckmin(int &u, int v) {
    if (u > v) return u = v, 1;
    return 0;
}
bool cmp(int i, int j) {
    return b[i].ft + b[i].sc < b[j].ft + b[j].sc;
}
void SweepLine() {
    for (int i = 1; i <= n; i++) id[i] = i;
    sort(id + 1, id + n + 1, cmp);
    map<int, int, greater<int>> active;
    for (int i = 1; i <= n; i++) {
        int u = id[i];
        for (map<int, int>::iterator it = active.lower_bound(b[u].ft); it != active.end(); active.erase(it++)) {
            int v = it->sc;
            if (b[u].ft - b[u].sc > b[v].ft - b[v].sc) break;
            G[u].push_back({b[u].ft - b[v].ft + b[u].sc - b[v].sc, v});
            G[v].push_back({b[u].ft - b[v].ft + b[u].sc - b[v].sc, u});
        }
        active[b[u].ft] = u;
    }
}
NeOWami main() {
    cin.tie(NULL)->sync_with_stdio(false);
    if(ifstream("DESERT.inp")) {
        freopen("DESERT.inp", "r", stdin);
        freopen("DESERT.out", "w", stdout);
    }
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i].ft >> a[i].sc;
    for (int i = 1; i <= n; i++) b[i] = a[i];
    for (int rot = 0; rot < 4; rot++) {
        SweepLine();
        for (int i = 1; i <= n; i++) {
            if (rot & 1) b[i].ft *= -1;
            else swap(b[i].ft, b[i].sc);
        }
    }
    fill(dist + 1, dist + n + 1, inf);
    dist[1] = 0;
    heapmin<pii> Q;
    Q.push({0, 1});
    while(!Q.empty()) {
        int old = Q.top().ft, u = Q.top().sc;
        Q.pop();
        for (pii item: G[u]) {
            int w = max(item.ft, old), v = item.sc;
            if (ckmin(dist[v], w)) {
                Q.push({w, v});
                par[v] = u;
            }
        }
    }
    vector<int> ans;
    for (int i = n; i; i = par[i]) ans.push_back(i);
    reverse(ans.begin(), ans.end());
    cout << dist[n] << "\n";
    for (int item: ans) cout << item << " ";
}