Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long LL;
- typedef unsigned long long ULL;
- typedef long double LD;
- #define all(a) a.begin(),a.end()
- #define rall(a) a.rbegin(),a.rend()
- #define X first
- #define Y second
- #define pb push_back
- #define sz(s) int64_t(s.size())
- #define make_unique(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
- const LL mod = 1e9 + 7;
- template<class T>
- istream& operator >> (istream& in, vector<T>& v){ for (auto &x : v) { in >> x; } return in; }
- template<class T, class U>
- istream& operator >> (istream& in, pair<T, U> & v){ in >> v.X >> v.Y;return in; }
- template<class T, class U>
- ostream& operator << (ostream& out, pair<T, U> & v){ out << v.X << " " << v.Y;return out; }
- template<class T, class U>
- void chkmax(T &a, U b) {
- a = max(a, (T)b);
- return;
- }
- template<class T, class U>
- void chkmin(T &a, U b) {
- a = min(a, (T)b);
- return;
- }
- LL ppow (LL x, LL s) {
- if (!s) return 1;
- if (!(s - 1)) return x % mod;
- if (s % 2) return (x * ppow (x, s - 1)) % mod;
- LL b = ppow (x, s / 2);
- return (b * b) % mod;
- }
- vector<int> zf (string s) {
- int n = sz(s);
- vector<int> z (n);
- for (int i = 1, l = 0, r = 0; i < n; i++) {
- if (i <= r)
- z[i] = min (r - i + 1, z[i - l]);
- while (i + z[i] < n && s[z[i]] == s[i + z[i]])
- z[i]++;
- if (i + z[i] - 1 > r)
- l = i, r = i + z[i] - 1;
- }
- return z;
- }
- vector<int> pf(string p) {
- int n = sz(p);
- vector<int> pref_fun(n, 0);
- for (int i = 1;i < n;i++) {
- int j = pref_fun[i - 1];
- while (j > 0 && p[i] != p[j])
- j = pref_fun[j - 1];
- if (p[i] == p[j])
- j++;
- pref_fun[i] = j;
- }
- return pref_fun;
- }
- vector<vector<int> > mul(vector<vector<int> > &a, vector<vector<int> > &b) {
- int n = sz(a);
- vector<vector<int> > c(n, vector<int> (n, 0));
- for (int i = 0;i < n;i++) {
- for (int j = 0;j < n;j++) {
- for (int k = 0;k < n;k++) {
- LL ga = a[i][k];
- ga *= b[k][j];
- ga %= mod;
- c[i][j] += ga;
- if (c[i][j] >= mod) {
- c[i][j] -= mod;
- }
- }
- }
- }
- return c;
- }
- vector<vector<int> > matrix_pow(vector<vector<int> > a, LL y) {
- int n = sz(a);
- vector<vector<int> > res(n, vector<int> (n, 0));
- for (int i = 0;i < n;i++) res[i][i] = 1;
- while (y) {
- if (y%2 == 1) {
- res = mul(res, a);
- y--;
- }else {
- a = mul(a, a);
- y /= 2;
- }
- }
- return res;
- }
- 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) {
- queue<pair<int,int> > q;
- q.push({x, y});
- d[x][y] = 0;
- auto check = [&](int x, int y) {
- return (x >= 0 && y >= 0 && x < n && y < m);
- };
- while (q.size()) {
- auto cur = q.front();
- q.pop();
- for (int i = 0;i < 8;i++) {
- int nx = cur.X + dx[i];
- int ny = cur.Y + dy[i];
- if (check(nx, ny)) {
- if (d[nx][ny] == -1) {
- d[nx][ny] = d[cur.X][cur.Y] + 1;
- way[nx][ny] = cur;
- q.push({nx, ny});
- }
- }
- }
- }
- }
- main(){
- ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
- // freopen("input.txt", "r", stdin);
- int n, m;
- cin >> n >> m;
- vector<int> p(2), q(2), xx(2), yy(2);
- cin >> p[0] >> q[0] >> p[1] >> q[1] >> xx[0] >> yy[0] >> xx[1] >> yy[1];
- xx[0]--;yy[0]--;
- xx[1]--;yy[1]--;
- vector<vector<vector<pair<int,int> > > > way(2, vector<vector<pair<int,int> > > (n, vector<pair<int,int> > (m, {-1, -1})));
- vector<vector<vector<int> > > d(2, vector<vector<int> > (n, vector<int> (m, -1)));
- vector<vector<int> > dx, dy;
- for (int i = 0;i < 2;i++) {
- dx.pb({-p[i], -p[i], p[i], p[i], -q[i], -q[i], q[i], q[i]});
- dy.pb({-q[i], q[i], -q[i], q[i], p[i], -p[i], -p[i], p[i]});
- }
- for (int i = 0;i < 2;i++) {
- bfs(n, m, dx[i], dy[i], way[i], d[i], xx[i], yy[i]);
- }
- int x = -1, y = -1;
- int mx = 1e9;
- for (int i = 0;i < n;i++) {
- for (int j = 0;j < m;j++) {
- if (d[0][i][j] == -1 || d[1][i][j] == -1) continue;
- if (abs(d[0][i][j] - d[1][i][j])%2 == 0) {
- if (max(d[0][i][j], d[1][i][j]) < mx) {
- mx = max(d[0][i][j], d[1][i][j]);
- x = i;
- y = j;
- }
- }
- }
- }
- if (x == -1) {
- cout << "-1";
- return 0;
- }
- vector<pair<int,int> > way1, way2;
- pair<int,int> cur = {x, y};
- while (true) {
- if (cur.X == -1) {
- break;
- }
- way1.pb(cur);
- cur = way[0][cur.X][cur.Y];
- }
- cur = {x, y};
- while (true) {
- if (cur.X == -1) {
- break;
- }
- way2.pb(cur);
- cur = way[1][cur.X][cur.Y];
- }
- auto check = [&](int x, int y) {
- return (x >= 0 && y >= 0 && x < n && y < m);
- };
- if (sz(way1) < sz(way2)) {
- pair<int,int> from = way1[sz(way1) - 1];
- pair<int,int> to = {-1, -1};
- for (int i = 0;i < 8;i++) {
- int nx = from.X + dx[0][i];
- int ny = from.Y + dy[0][i];
- if (check(nx, ny)) {
- to = {nx, ny};
- }
- }
- pair<int,int> bad = {-1, -1};
- if (to == bad) {
- cout << "-1";
- return 0;
- }
- while (sz(way1) < sz(way2)) {
- way1.pb(to);
- way1.pb(from);
- }
- }else if (sz(way1) > sz(way2)) {
- pair<int,int> from = way2[sz(way2) - 1];
- pair<int,int> to = {-1, -1};
- for (int i = 0;i < 8;i++) {
- int nx = from.X + dx[1][i];
- int ny = from.Y + dy[1][i];
- if (check(nx, ny)) {
- to = {nx, ny};
- }
- }
- pair<int,int> bad = {-1, -1};
- if (to == bad) {
- cout << "-1";
- return 0;
- }
- while (sz(way2) < sz(way1)) {
- way2.pb(to);
- way2.pb(from);
- }
- }
- cout << sz(way1) - 1 << '\n';
- reverse(all(way1));
- reverse(all(way2));
- for (int i = 0;i < sz(way1);i++) {
- cout << way1[i].X + 1 << " " << way1[i].Y + 1 << " " << way2[i].X + 1 << " " << way2[i].Y + 1 << '\n';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement