Advertisement
trungore10

Untitled

Mar 14th, 2019
120
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.66 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define X       first
  3. #define Y       second
  4. using namespace std;
  5.  
  6. bool debug;
  7.  
  8. void Read(int &val) {
  9.     val = 0; char c;
  10.     do { c = getchar(); } while (!isdigit(c) && c != '-');
  11.     bool Minus = false; if (c == '-') { Minus = true; c = getchar(); }
  12.     while (isdigit(c)) { val = val * 10 + c - '0'; c = getchar(); }
  13.     if (Minus) val = -val;
  14. }
  15. void Write(int val) {
  16.     if (val < 0) putchar('-'), Write(-val);
  17.     else if (val < 10) putchar('0' + val);
  18.     else Write(val/10), putchar('0' + val%10);
  19. }
  20.  
  21. typedef pair<int, int> ii;
  22. struct data {
  23.     int id, X, Y, step;
  24.     data() {}; data(int id, int X, int Y, int step) : id(id), X(X), Y(Y), step(step) {};
  25. };
  26.  
  27. const int N = 1e6 + 4, oo = 1e9 + 7;
  28. int limX, limY, q, n, idS, idT;
  29. ii a[N], org[N], S, T;
  30.  
  31. vector<int> rarX, rarY;
  32. int xmax, ymax;
  33.  
  34. void compress() {
  35.     for (int i = 1; i <= n; ++i) {
  36.         rarX.push_back(a[i].X);
  37.         rarY.push_back(a[i].Y);
  38.     }
  39.  
  40.     sort(rarX.begin(), rarX.end());
  41.     rarX.resize(unique(rarX.begin(), rarX.end()) - rarX.begin());
  42.  
  43.     sort(rarY.begin(), rarY.end());
  44.     rarY.resize(unique(rarY.begin(), rarY.end()) - rarY.begin());
  45.  
  46.     for (int i = 1; i <= n; ++i) {
  47.         a[i].X = lower_bound(rarX.begin(), rarX.end(), a[i].X) - rarX.begin() + 1;
  48.         a[i].Y = lower_bound(rarY.begin(), rarY.end(), a[i].Y) - rarY.begin() + 1;
  49.     }
  50.  
  51.     xmax = (int) rarX.size();
  52.     ymax = (int) rarY.size();
  53. }
  54.  
  55. int val[N][2], Pos[N][2], par[N][2];
  56. vector<ii> arr[2];
  57.  
  58. int getRoot(int u, int id) { return (par[u][id] < 0) ? u : (par[u][id] = getRoot(par[u][id], id)); }
  59. void Merge(int u, int v, int id, int orePos) {
  60.     u = getRoot(u, id); v = getRoot(v, id);
  61.     if (u == v) return;
  62.    
  63.     if (par[u][id] > par[v][id]) swap(u, v);
  64.     par[u][id] += par[v][id];
  65.     par[v][id] = u;
  66.  
  67.     Pos[u][id] = orePos;
  68. }
  69.  
  70. void prepare() {
  71.     for (int i = 1; i <= xmax; ++i) val[i][0] = oo, val[i][1] = -oo;
  72.     for (int i = 1; i <= n; ++i) {
  73.         val[a[i].X][0] = min(val[a[i].X][0], a[i].Y);
  74.         val[a[i].X][1] = max(val[a[i].X][1], a[i].Y);
  75.     }
  76.  
  77.     for (int id = 0; id <= 1; ++id) {
  78.         arr[id].clear();
  79.         for (int i = 1; i <= xmax; ++i) par[i][id] = -1, Pos[i][id] = -1;
  80.  
  81.         int i = (id == 0) ? 1 : xmax, prevI, mul = (id == 0) ? 1 : -1;
  82.         while (true) {
  83.             if (arr[id].empty()) {
  84.                 arr[id].push_back(ii(i, val[i][id]));
  85.                 Pos[i][id] = 0;
  86.             }
  87.             else {
  88.                 if (arr[id].back().Y * mul >= val[i][id] * mul) {
  89.                     arr[id].push_back(ii(i, val[i][id]));
  90.                     Pos[i][id] = (int) arr[id].size()-1;
  91.                 }
  92.                 else Merge(i, prevI, id, Pos[getRoot(prevI, id)][id]);
  93.             }
  94.  
  95.             prevI = i;
  96.             if (id == 0 && i == xmax) break;
  97.             if (id == 1 && i ==  1  ) break;
  98.             if (id == 0) ++i; else --i;
  99.         }
  100.     }
  101. }
  102.  
  103. queue<data> Q;
  104. bool vis[N];
  105.  
  106. int process(int idStart) {
  107.         // for (int i = 1; i <= n; ++i) cerr << a[i].X << " " << a[i].Y << '\n';
  108.         for (ii u : arr[1]) cerr << u.X << " " << u.Y << '\n';
  109.         exit(0);
  110.  
  111.     while (Q.size()) Q.pop();
  112.     Q.push(data(idStart, S.X, S.Y, 1));
  113.  
  114.     for (int i = 0; i <= xmax; ++i) vis[i] = false;
  115.  
  116.     while (Q.size()) {
  117.         int id = Q.front().id, x = Q.front().X, y = Q.front().Y, step = Q.front().step; Q.pop();
  118.         int mul = (id == 0) ? 1 : -1;
  119.  
  120.         if (x == T.X && y == T.Y) return step;
  121.         if (x <= T.X && y <= T.Y) return step+1;
  122.         if (x >= T.X && y >= T.Y) return step+1;
  123.  
  124.         int pos = Pos[getRoot(x, id)][id];
  125.  
  126.         while (pos >= 0) {
  127.             if (vis[pos] && pos == 0) break;
  128.  
  129.             if (arr[id][pos].X * mul <= x * mul && arr[id][pos].Y * mul <= y * mul) {
  130.                 if (pos > 0) Merge(arr[id][pos].X, arr[id][pos-1].X, id, Pos[getRoot(arr[id][pos-1].X, id)][id]);
  131.                
  132.                 if (!vis[pos]) {
  133.                     int cc = step+1;
  134.                     if (arr[id][pos].X == x && arr[id][pos].Y == y) cc = step;
  135.  
  136.                     Q.push(data(1-id, arr[id][pos].X, arr[id][pos].Y, cc));
  137.                 }
  138.                 vis[pos] = true;
  139.             }
  140.             else break;
  141.  
  142.             pos = Pos[getRoot(arr[id][pos].first, id)][id];
  143.         }
  144.     }
  145.     return oo;
  146. }
  147.  
  148. void sol() {
  149.     compress();
  150.     for (int i = 1; i <= n; ++i) org[i] = a[i];
  151.  
  152.     sort(a+1, a+n+1, [] (ii b, ii c) {
  153.         return b.first < c.first || (b.first == c.first && b.second > c.second);
  154.     });
  155.        
  156.     Read(q);
  157.     while (q--) {
  158.         Read(idS); Read(idT);
  159.         S = org[idS]; T = org[idT];
  160.  
  161.         prepare();
  162.         int ans1 = process(1);
  163.  
  164.         prepare();
  165.         int ans0 = process(0);
  166.  
  167.         int res = min(ans0, ans1) - 2;
  168.         if (res == oo-2) Write(-1); else Write(res);
  169.         putchar('\n');
  170.     }
  171. }
  172.  
  173. int main() {
  174.     if (fopen("input.txt", "r")) {
  175.         freopen("input.txt", "r", stdin);
  176.         freopen("output.txt", "w", stdout);
  177.     }
  178.     else if (fopen("minmov.inp", "r")) {
  179.         freopen("minmov.inp", "r", stdin);
  180.         freopen("minmov.out", "w", stdout);
  181.     }
  182.  
  183.     Read(limX); Read(limY); Read(n);
  184.     for (int i = 1; i <= n; ++i) {
  185.         Read(a[i].X); Read(a[i].Y);
  186.         // a[i].Y = -a[i].Y;
  187.     }
  188.  
  189.     sol();
  190.  
  191.     return 0;
  192. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement