Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define X first
- #define Y second
- using namespace std;
- bool debug;
- void Read(int &val) {
- val = 0; char c;
- do { c = getchar(); } while (!isdigit(c) && c != '-');
- bool Minus = false; if (c == '-') { Minus = true; c = getchar(); }
- while (isdigit(c)) { val = val * 10 + c - '0'; c = getchar(); }
- if (Minus) val = -val;
- }
- void Write(int val) {
- if (val < 0) putchar('-'), Write(-val);
- else if (val < 10) putchar('0' + val);
- else Write(val/10), putchar('0' + val%10);
- }
- typedef pair<int, int> ii;
- struct data {
- int id, X, Y, step;
- data() {}; data(int id, int X, int Y, int step) : id(id), X(X), Y(Y), step(step) {};
- };
- const int N = 1e6 + 4, oo = 1e9 + 7;
- int limX, limY, q, n, idS, idT;
- ii a[N], org[N], S, T;
- vector<int> rarX, rarY;
- int xmax, ymax;
- void compress() {
- for (int i = 1; i <= n; ++i) {
- rarX.push_back(a[i].X);
- rarY.push_back(a[i].Y);
- }
- sort(rarX.begin(), rarX.end());
- rarX.resize(unique(rarX.begin(), rarX.end()) - rarX.begin());
- sort(rarY.begin(), rarY.end());
- rarY.resize(unique(rarY.begin(), rarY.end()) - rarY.begin());
- for (int i = 1; i <= n; ++i) {
- a[i].X = lower_bound(rarX.begin(), rarX.end(), a[i].X) - rarX.begin() + 1;
- a[i].Y = lower_bound(rarY.begin(), rarY.end(), a[i].Y) - rarY.begin() + 1;
- }
- xmax = (int) rarX.size();
- ymax = (int) rarY.size();
- }
- int val[N][2], Pos[N][2], par[N][2];
- vector<ii> arr[2];
- int getRoot(int u, int id) { return (par[u][id] < 0) ? u : (par[u][id] = getRoot(par[u][id], id)); }
- void Merge(int u, int v, int id, int orePos) {
- u = getRoot(u, id); v = getRoot(v, id);
- if (u == v) return;
- if (par[u][id] > par[v][id]) swap(u, v);
- par[u][id] += par[v][id];
- par[v][id] = u;
- Pos[u][id] = orePos;
- }
- void prepare() {
- for (int i = 1; i <= xmax; ++i) val[i][0] = oo, val[i][1] = -oo;
- for (int i = 1; i <= n; ++i) {
- val[a[i].X][0] = min(val[a[i].X][0], a[i].Y);
- val[a[i].X][1] = max(val[a[i].X][1], a[i].Y);
- }
- for (int id = 0; id <= 1; ++id) {
- arr[id].clear();
- for (int i = 1; i <= xmax; ++i) par[i][id] = -1, Pos[i][id] = -1;
- int i = (id == 0) ? 1 : xmax, prevI, mul = (id == 0) ? 1 : -1;
- while (true) {
- if (arr[id].empty()) {
- arr[id].push_back(ii(i, val[i][id]));
- Pos[i][id] = 0;
- }
- else {
- if (arr[id].back().Y * mul >= val[i][id] * mul) {
- arr[id].push_back(ii(i, val[i][id]));
- Pos[i][id] = (int) arr[id].size()-1;
- }
- else Merge(i, prevI, id, Pos[getRoot(prevI, id)][id]);
- }
- prevI = i;
- if (id == 0 && i == xmax) break;
- if (id == 1 && i == 1 ) break;
- if (id == 0) ++i; else --i;
- }
- }
- }
- queue<data> Q;
- bool vis[N];
- int process(int idStart) {
- // for (int i = 1; i <= n; ++i) cerr << a[i].X << " " << a[i].Y << '\n';
- for (ii u : arr[1]) cerr << u.X << " " << u.Y << '\n';
- exit(0);
- while (Q.size()) Q.pop();
- Q.push(data(idStart, S.X, S.Y, 1));
- for (int i = 0; i <= xmax; ++i) vis[i] = false;
- while (Q.size()) {
- int id = Q.front().id, x = Q.front().X, y = Q.front().Y, step = Q.front().step; Q.pop();
- int mul = (id == 0) ? 1 : -1;
- if (x == T.X && y == T.Y) return step;
- if (x <= T.X && y <= T.Y) return step+1;
- if (x >= T.X && y >= T.Y) return step+1;
- int pos = Pos[getRoot(x, id)][id];
- while (pos >= 0) {
- if (vis[pos] && pos == 0) break;
- if (arr[id][pos].X * mul <= x * mul && arr[id][pos].Y * mul <= y * mul) {
- if (pos > 0) Merge(arr[id][pos].X, arr[id][pos-1].X, id, Pos[getRoot(arr[id][pos-1].X, id)][id]);
- if (!vis[pos]) {
- int cc = step+1;
- if (arr[id][pos].X == x && arr[id][pos].Y == y) cc = step;
- Q.push(data(1-id, arr[id][pos].X, arr[id][pos].Y, cc));
- }
- vis[pos] = true;
- }
- else break;
- pos = Pos[getRoot(arr[id][pos].first, id)][id];
- }
- }
- return oo;
- }
- void sol() {
- compress();
- for (int i = 1; i <= n; ++i) org[i] = a[i];
- sort(a+1, a+n+1, [] (ii b, ii c) {
- return b.first < c.first || (b.first == c.first && b.second > c.second);
- });
- Read(q);
- while (q--) {
- Read(idS); Read(idT);
- S = org[idS]; T = org[idT];
- prepare();
- int ans1 = process(1);
- prepare();
- int ans0 = process(0);
- int res = min(ans0, ans1) - 2;
- if (res == oo-2) Write(-1); else Write(res);
- putchar('\n');
- }
- }
- int main() {
- if (fopen("input.txt", "r")) {
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- }
- else if (fopen("minmov.inp", "r")) {
- freopen("minmov.inp", "r", stdin);
- freopen("minmov.out", "w", stdout);
- }
- Read(limX); Read(limY); Read(n);
- for (int i = 1; i <= n; ++i) {
- Read(a[i].X); Read(a[i].Y);
- // a[i].Y = -a[i].Y;
- }
- sol();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement