Advertisement
Guest User

Untitled

a guest
Apr 4th, 2020
146
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.58 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long LL;
  6. typedef unsigned long long ULL;
  7. typedef long double LD;
  8.  
  9. #define all(a) a.begin(),a.end()
  10. #define rall(a) a.rbegin(),a.rend()
  11. #define X first
  12. #define Y second
  13. #define pb push_back
  14. #define sz(s) int64_t(s.size())
  15. #define make_unique(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
  16.  
  17. const LL mod = 1e9 + 7;
  18.  
  19.  
  20. template<class T>
  21. istream& operator >> (istream& in, vector<T>& v){ for (auto &x : v) { in >> x; } return in; }
  22.  
  23. template<class T, class U>
  24. istream& operator >> (istream& in, pair<T, U> & v){ in >> v.X >> v.Y;return in; }
  25.  
  26. template<class T, class U>
  27. ostream& operator << (ostream& out, pair<T, U> & v){ out << v.X << " " << v.Y;return out; }
  28.  
  29.  
  30. template<class T, class U>
  31. void chkmax(T &a, U b) {
  32.     a = max(a, (T)b);
  33.     return;
  34. }
  35.  
  36. template<class T, class U>
  37. void chkmin(T &a, U b) {
  38.     a = min(a, (T)b);
  39.     return;
  40. }
  41.  
  42. LL ppow (LL x, LL s) {
  43.     if (!s) return 1;
  44.     if (!(s - 1)) return x % mod;
  45.     if (s % 2) return (x * ppow (x, s - 1)) % mod;
  46.     LL b = ppow (x, s / 2);
  47.     return (b * b) % mod;
  48. }
  49.  
  50. vector<int> zf (string s) {
  51.  
  52.     int n = sz(s);
  53.  
  54.     vector<int> z (n);
  55.  
  56.     for (int i = 1, l = 0, r = 0; i < n; i++) {
  57.  
  58.         if (i <= r)
  59.             z[i] = min (r - i + 1, z[i - l]);
  60.  
  61.         while (i + z[i] < n && s[z[i]] == s[i + z[i]])
  62.             z[i]++;
  63.  
  64.         if (i + z[i] - 1 > r)
  65.             l = i,  r = i + z[i] - 1;
  66.  
  67.     }
  68.  
  69.     return z;
  70.  
  71. }
  72.  
  73. vector<int> pf(string p) {
  74.     int n = sz(p);
  75.     vector<int> pref_fun(n, 0);
  76.  
  77.     for (int i = 1;i < n;i++) {
  78.         int j = pref_fun[i - 1];
  79.         while (j > 0 && p[i] != p[j])
  80.             j = pref_fun[j - 1];
  81.         if (p[i] == p[j])
  82.             j++;
  83.         pref_fun[i] = j;
  84.     }
  85.     return pref_fun;
  86. }
  87.  
  88. vector<vector<int> > mul(vector<vector<int> > &a, vector<vector<int> > &b) {
  89.     int n = sz(a);
  90.     vector<vector<int> > c(n, vector<int> (n, 0));
  91.  
  92.     for (int i = 0;i < n;i++) {
  93.         for (int j = 0;j < n;j++) {
  94.             for (int k = 0;k < n;k++) {
  95.                 LL ga = a[i][k];
  96.                 ga *= b[k][j];
  97.                 ga %= mod;
  98.                 c[i][j] += ga;
  99.                 if (c[i][j] >= mod) {
  100.                     c[i][j] -= mod;
  101.                 }
  102.             }
  103.         }
  104.     }
  105.  
  106.     return c;
  107. }
  108.  
  109. vector<vector<int> > matrix_pow(vector<vector<int> > a, LL y) {
  110.     int n = sz(a);
  111.     vector<vector<int> > res(n, vector<int> (n, 0));
  112.     for (int i = 0;i < n;i++) res[i][i] = 1;
  113.     while (y) {
  114.         if (y%2 == 1) {
  115.             res = mul(res, a);
  116.             y--;
  117.         }else {
  118.             a = mul(a, a);
  119.             y /= 2;
  120.         }
  121.     }
  122.     return res;
  123. }
  124.  
  125. void bfs(int n, int m, vector<int> &dx, vector<int> &dy, vector<vector<pair<int,int> > > &way, vector<vector<int> > &d, int x, int y) {
  126.     queue<pair<int,int> > q;
  127.     q.push({x, y});
  128.     d[x][y] = 0;
  129.     auto check = [&](int x, int y) {
  130.         return (x >= 0 && y >= 0 && x < n && y < m);
  131.     };
  132.     while (q.size()) {
  133.         auto cur = q.front();
  134.         q.pop();
  135.         for (int i = 0;i < 8;i++) {
  136.             int nx = cur.X + dx[i];
  137.             int ny = cur.Y + dy[i];
  138.             if (check(nx, ny)) {
  139.                 if (d[nx][ny] == -1) {
  140.                     d[nx][ny] = d[cur.X][cur.Y] + 1;
  141.                     way[nx][ny] = cur;
  142.                     q.push({nx, ny});
  143.                 }
  144.             }
  145.         }
  146.     }
  147. }
  148.  
  149. main(){
  150.     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  151. //    freopen("input.txt", "r", stdin);
  152.     int n, m;
  153.     cin >> n >> m;
  154.     vector<int> p(2), q(2), xx(2), yy(2);
  155.     cin >> p[0] >> q[0] >> p[1] >> q[1] >> xx[0] >> yy[0] >> xx[1] >> yy[1];
  156.     xx[0]--;yy[0]--;
  157.     xx[1]--;yy[1]--;
  158.  
  159.     vector<vector<vector<pair<int,int> > > > way(2, vector<vector<pair<int,int> > > (n, vector<pair<int,int> > (m, {-1, -1})));
  160.     vector<vector<vector<int> > > d(2, vector<vector<int> > (n, vector<int> (m, -1)));
  161.  
  162.     vector<vector<int> > dx, dy;
  163.  
  164.     for (int i = 0;i < 2;i++) {
  165.         dx.pb({-p[i], -p[i], p[i], p[i], -q[i], -q[i], q[i], q[i]});
  166.         dy.pb({-q[i], q[i], -q[i], q[i], p[i], -p[i], -p[i], p[i]});
  167.     }
  168.  
  169.     for (int i = 0;i < 2;i++) {
  170.         bfs(n, m, dx[i], dy[i], way[i], d[i], xx[i], yy[i]);
  171.     }
  172.  
  173.     int x = -1, y = -1;
  174.     int mx = 1e9;
  175.     for (int i = 0;i < n;i++) {
  176.         for (int j = 0;j < m;j++) {
  177.             if (d[0][i][j] == -1 || d[1][i][j] == -1) continue;
  178.             if (abs(d[0][i][j] - d[1][i][j])%2 == 0) {
  179.                 if (max(d[0][i][j], d[1][i][j]) < mx) {
  180.                     mx = max(d[0][i][j], d[1][i][j]);
  181.                     x = i;
  182.                     y = j;
  183.                 }
  184.             }
  185.         }
  186.     }
  187.     if (x == -1) {
  188.         cout << "-1";
  189.         return 0;
  190.     }
  191.  
  192.     vector<pair<int,int> > way1, way2;
  193.  
  194.     pair<int,int> cur = {x, y};
  195.     while (true) {
  196.         if (cur.X == -1) {
  197.             break;
  198.         }
  199.         way1.pb(cur);
  200.         cur = way[0][cur.X][cur.Y];
  201.     }
  202.  
  203.     cur = {x, y};
  204.     while (true) {
  205.         if (cur.X == -1) {
  206.             break;
  207.         }
  208.         way2.pb(cur);
  209.         cur = way[1][cur.X][cur.Y];
  210.     }
  211.     auto check = [&](int x, int y) {
  212.         return (x >= 0 && y >= 0 && x < n && y < m);
  213.     };
  214.     if (sz(way1) < sz(way2)) {
  215.         pair<int,int> from = way1[sz(way1) - 1];
  216.         pair<int,int> to = {-1, -1};
  217.         for (int i = 0;i < 8;i++) {
  218.             int nx = from.X + dx[0][i];
  219.             int ny = from.Y + dy[0][i];
  220.             if (check(nx, ny)) {
  221.                 to = {nx, ny};
  222.             }
  223.         }
  224.         pair<int,int> bad = {-1, -1};
  225.         if (to == bad) {
  226.             cout << "-1";
  227.             return 0;
  228.         }
  229.         while (sz(way1) < sz(way2)) {
  230.             way1.pb(to);
  231.             way1.pb(from);
  232.         }
  233.     }else if (sz(way1) > sz(way2)) {
  234.         pair<int,int> from = way2[sz(way2) - 1];
  235.         pair<int,int> to = {-1, -1};
  236.         for (int i = 0;i < 8;i++) {
  237.             int nx = from.X + dx[1][i];
  238.             int ny = from.Y + dy[1][i];
  239.             if (check(nx, ny)) {
  240.                 to = {nx, ny};
  241.             }
  242.         }
  243.         pair<int,int> bad = {-1, -1};
  244.         if (to == bad) {
  245.             cout << "-1";
  246.             return 0;
  247.         }
  248.         while (sz(way2) < sz(way1)) {
  249.             way2.pb(to);
  250.             way2.pb(from);
  251.         }
  252.     }
  253.     cout << sz(way1) - 1 << '\n';
  254.     reverse(all(way1));
  255.     reverse(all(way2));
  256.     for (int i = 0;i < sz(way1);i++) {
  257.         cout << way1[i].X + 1 << " " << way1[i].Y + 1 << " " << way2[i].X + 1 << " " << way2[i].Y + 1 << '\n';
  258.     }
  259.  
  260.     return 0;
  261. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement