#include <bits/stdc++.h> using namespace std; const int N = 100'000 + 10; int s, t, u, v, n; struct Rec { int x, y, u, v; friend istream& operator >> (istream& is, Rec& rhs) { return is >> rhs.x >> rhs.u >> rhs.y >> rhs.v; } } rec[N]; namespace sub2 { bool checkCondition() { return n <= 1000; } const int SZ = 2000 + 10; bool go[SZ][SZ][4]; const int dX[] = {1, 0, -1, 0}, dY[] = {0, 1, 0, -1}; int f[SZ][SZ][4]; void solve() { vector<int> allX{s, u}, allY{t, v}; for (int i = 1; i <= n; ++i) { allX.push_back(rec[i].x); allX.push_back(rec[i].u); allY.push_back(rec[i].y); allY.push_back(rec[i].v); } sort(allX.begin(), allX.end()); allX.erase(unique(allX.begin(), allX.end()), allX.end()); sort(allY.begin(), allY.end()); allY.erase(unique(allY.begin(), allY.end()), allY.end()); s = upper_bound(allX.begin(), allX.end(), s) - allX.begin(); t = upper_bound(allY.begin(), allY.end(), t) - allY.begin(); u = upper_bound(allX.begin(), allX.end(), u) - allX.begin(); v = upper_bound(allY.begin(), allY.end(), v) - allY.begin(); memset(go, true, sizeof go); for (int iR = 1; iR <= n; ++iR) { auto& x = rec[iR].x; auto& y = rec[iR].y; auto& u = rec[iR].u; auto& v = rec[iR].v; x = upper_bound(allX.begin(), allX.end(), x) - allX.begin(); y = upper_bound(allY.begin(), allY.end(), y) - allY.begin(); u = upper_bound(allX.begin(), allX.end(), u) - allX.begin(); v = upper_bound(allY.begin(), allY.end(), v) - allY.begin(); for (int i = x + 1; i < u; ++i) { go[i][y][1] = false; go[i][v][3] = false; } for (int j = y + 1; j < v; ++j) { go[x][j][0] = false; go[u][j][2] = false; } } memset(f, 63, sizeof f); deque<tuple<int, int, int>> q; for (int d = 0; d < 4; ++d) { q.emplace_back(s, t, d); f[s][t][d] = 0; } while (q.size()) { int x, y, pD; tie(x, y, pD) = q.back(); q.pop_back(); for (int d = 0; d < 4; ++d) { int nX = x + dX[d], nY = y + dY[d]; if (!nX || !nY || nX > (int)allX.size() || nY > (int)allY.size() || !go[x][y][d]) continue; int val = f[x][y][pD] + (pD != d); if (f[nX][nY][d] > val) { f[nX][nY][d] = val; if (val == f[x][y][pD]) q.emplace_back(nX, nY, d); else q.emplace_front(nX, nY, d); } } } int answer = 1'000'000'000; for (int d = 0; d < 4; ++d) { answer = min(answer, f[u][v][d]); } cout << answer + 1 << "\n"; } } int32_t main() { cin.tie(0)->sync_with_stdio(0); if (fopen("input.txt", "r")) { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); } if (fopen("golf.inp", "r")) { freopen("golf.inp", "r", stdin); freopen("golf.out", "w", stdout); } cin >> s >> t >> u >> v >> n; for (int i = 1; i <= n; ++i) cin >> rec[i]; if (sub2::checkCondition()) { sub2::solve(); return 0; } }

golf.cpp: In function 'int32_t main()':
golf.cpp:103:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp:104:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp:107:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |         freopen("golf.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp:108:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         freopen("golf.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~