#include #include #include #include using namespace __gnu_pbds; using namespace std; #define endl "\n" #define mp make_pair #define st first #define nd second #define pii pair #define pb push_back #define _upgrade ios_base::sync_with_stdio(0), cout.setf(ios::fixed), cout.precision(10), cin.tie(0), cout.tie(0); #define rep(i, n) for (int i = 0; i < (n); ++i) #define fwd(i, a, b) for (int i = (a); i < (b); ++i) #define trav(a, x) for (auto &a : x) #define all(c) (c).begin(), (c).end() #define sz(X) (int)((X).size()) typedef long double ld; typedef unsigned long long ull; typedef long long ll; typedef tree, rb_tree_tag, tree_order_statistics_node_update> indexed_set; // find_by_order(x) <-returns x-th element order_of_key(x) <- returns order of element x // mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());uniform_int_distribution distr(0, 1e9);auto my_rand = bind(distr, gen); // my_rand() zwraca teraz liczbe z przedzialu [a, b] #ifdef LOCAL ostream &operator<<(ostream &out, string str) { for (char c : str) out << c; return out; } template ostream &operator<<(ostream &out, pair p) { return out << "(" << p.st << ", " << p.nd << ")"; } template ostream &operator<<(ostream &out, tuple p) { auto &[a, b, c] = p; return out << "(" << a << ", " << b << ", " << c << ")"; } template auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) { out << '{'; for (auto it = a.begin(); it != a.end(); it = next(it)) out << (it != a.begin() ? ", " : "") << *it; return out << '}'; } void dump() { cerr << "\n"; } template void dump(T a, Ts... x) { cerr << a << ", "; dump(x...); } #define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__) #else #define debug(...) 42 #endif #define int long long int w, h; pii s, e; vector> H; // Code from kcatl lib template int sgn(T x) { return (x > 0) - (x < 0); } template struct Point { typedef Point P; T x, y; explicit Point(T x = 0, T y = 0) : x(x), y(y) {} bool operator<(P p) const { return tie(x, y) < tie(p.x, p.y); } bool operator==(P p) const { return tie(x, y) == tie(p.x, p.y); } P operator+(P p) const { return P(x + p.x, y + p.y); } P operator-(P p) const { return P(x - p.x, y - p.y); } P operator*(T d) const { return P(x * d, y * d); } P operator/(T d) const { return P(x / d, y / d); } T dot(P p) const { return x * p.x + y * p.y; } T cross(P p) const { return x * p.y - y * p.x; } T cross(P a, P b) const { return (a - *this).cross(b - *this); } T dist2() const { return x * x + y * y; } double dist() const { return sqrt((double)dist2()); } // angle to x-axis in interval [-pi, pi] double angle() const { return atan2(y, x); } P unit() const { return *this / dist(); } // makes dist()=1 P perp() const { return P(-y, x); } // rotates +90 degrees P normal() const { return perp().unit(); } // returns point rotated 'a' radians ccw around the origin P rotate(double a) const { return P(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a)); } friend ostream &operator<<(ostream &os, P p) { return os << "(" << p.x << "," << p.y << ")"; } }; template bool onSegment(P s, P e, P p) { return p.cross(s, e) == 0 && (s - p).dot(e - p) <= 0; } template vector

segInter(P a, P b, P c, P d) { auto oa = c.cross(d, a), ob = c.cross(d, b), oc = a.cross(b, c), od = a.cross(b, d); // Checks i f intersection i s single non−endpoint point . if (sgn(oa) * sgn(ob) < 0 && sgn(oc) * sgn(od) < 0) return {(a * ob - b * oa) / (ob - oa)}; set

s; if (onSegment(c, d, a)) s.insert(a); if (onSegment(c, d, b)) s.insert(b); if (onSegment(a, b, c)) s.insert(c); if (onSegment(a, b, d)) s.insert(d); return {all(s)}; } Point getLdl(pii p) { return Point(p.st, p.nd); } Point getLd(pair p) { return Point(p.st, p.nd); } Point getLl(pii p) { return Point(p.st, p.nd); } const ld eps = 1e-6; ld get(pair p) { auto [a, b] = p.st; auto [c, d] = p.nd; return abs(abs(H[a][b] - H[c][d])); } ld get(int h1, int h2, int h3, int h4) { // pytanie czy tu maks czy min auto h = min(h3, h4); if (h < min(h1, h2)) return abs(h1 - h2); return abs(h1 - h) + abs(h2 - h); } ld get(pii p, bool prawo) { auto [a, b] = p; if (prawo) { auto h1 = H[a][b]; auto h2 = H[a - 1][b - 1]; return get(h1, h2, H[a - 1][b], H[a][b - 1]); } else { auto h1 = H[a - 1][b]; auto h2 = H[a][b - 1]; return get(h1, h2, H[a - 1][b - 1], H[a][b]); } } void rev() { vector> Q(sz(H[0]), vector(sz(H))); rep(i, sz(H)) rep(j, sz(H[0])) Q[j][i] = H[i][j]; H = Q; } int32_t main() { _upgrade; cin >> w >> h; cin >> s.st >> s.nd; cin >> e.st >> e.nd; // swap(e.st, e.nd); // swap(s.st, s.nd); if (s.st > e.st) swap(s, e); debug(s, e); H.resize(h / 2); rep(i, h / 2) { rep(j, w / 2) { int c; cin >> c; H[i].push_back(c); } } debug(H); vector> W; // ZERO vector X; rep(i, w / 2 + 10) rep(j, h / 2 + 10) { auto s1 = getLl(s); auto e1 = getLl(e); auto p = getLl({2 * i, 2 * j}); if (onSegment(e1, s1, p)) X.push_back({i, j}); } // JEDEN rep(i, w / 2 + 10) rep(j, h / 2 + 10) { auto s1 = getLdl(s); auto e1 = getLdl(e); auto s2 = getLd({2.0 * i, 2.0 * j}); auto e2 = getLd({2.0 * i, 2.0 * j + 2}); bool OK = false; { auto s1 = getLl(s); auto e1 = getLl(e); auto p1 = getLl({2 * i, 2 * j}); auto p2 = getLl({2 * i, 2 * j + 2}); OK = (!onSegment(s1, e1, p1)) && (!onSegment(s1, e1, p2)); } auto r = segInter(s1, e1, s2, e2); if (sz(r) && OK) W.push_back({{i, j}, {i - 1, j}}); } // DWA rep(i, w / 2 + 10) rep(j, h / 2 + 10) { auto s1 = getLdl(s); auto e1 = getLdl(e); auto s2 = getLd({2.0 * i, 2.0 * j}); auto e2 = getLd({2.0 * i + 2, 2.0 * j}); bool OK = false; { auto s1 = getLl(s); auto e1 = getLl(e); auto p1 = getLl({2 * i, 2 * j}); auto p2 = getLl({2 * i + 2, 2 * j}); OK = (!onSegment(s1, e1, p1)) && (!onSegment(s1, e1, p2)); } auto r = segInter(s1, e1, s2, e2); // debug(r); if (sz(r) && OK) W.push_back({{i, j}, {i, j - 1}}); } // TRZY rev(); debug(H); debug(W); debug(X); ld res = (getLdl(s) - getLdl(e)).dist(); debug(res); for (auto [a, b] : W) { res += get({a, b}); debug(res); } for (auto p : X) res += get(p, s.nd < e.nd); debug(res); cout << res << endl; }