#ifndef LOCAL #pragma GCC optimize("O3") #endif #include using namespace std; #define sim template muu & operator<<( #define ris return *this #define R22(r) sim> typename enable_if<1 r sizeof(dud(0)),muu&>::type operator<<(c g) { sim> struct rge {c b, e;}; sim> rge range(c i, c j) {return {i, j};} sim> auto dud(c*r)->decltype(cerr << *r); sim> char dud(...); struct muu { #ifdef LOCAL stringstream a; ~muu() {cerr << a.str() << endl;} R22(<) a << boolalpha << g; ris;} R22(==) ris << range(begin(g), end(g));} sim, class b mor pair r) {ris << "(" << r.first << ", " << r.second << ")";} sim mor rge u) { a << "["; for (c i = u.b; i != u.e; ++i) *this << ", " + 2 * (i == u.b) << *i; ris << "]"; } #define qel(t) sim, class d, class...e mor t r) {ris << *(d*)&r;} qel(stack) qel(queue) qel(priority_queue) template r) { a << "("; int q = 0; apply([&](c...x){((*this << ", " + 2 * !q++ << x), ...);}, r); ris << ")"; } #else sim mor const c&){ris;} #endif }; #define imie(r...) "[" #r ": " << (r) << "] " #define arr(a, i) "[" #a imie(i) ": " << a[i] << "] " #define arr2(a, i, j) "[" #a imie(i) imie(j) ": " << a[i][j] << "] " #define range(a, b) "[[" #a ", " #b "): " << range(a, b) << "] " #define debug muu() << __FUNCTION__ << "#" << __LINE__ << ": " using ll = long long; using ld = long double; using unt = unsigned int; using pii = pair; using vpii = vector ; using ull = unsigned long long; using vi = vector; using Pii = pii; using vll = vector ; sim> void mini(c &a, const c& b) {if (a > b) a = b;} sim> void maxi(c &a, const c& b) {if (a < b) a = b;} ld K(ld x) { return x * x; } ll vec(pii a, pii b) { return a.first * 1ll * b.second - a.second * 1ll * b.first; } //Operatory na parach: (a, b) + c = (a + c, b + c), (a, b) + (c, d) = (a + c, b + d), a + (b, c) = (a + b, a + c) //(a, b) += (c, d) -> (a + c, b + d) (a, b) += c -> (a + c, b + c) //Automatycznie przenosi się na operatory na większych krotkach, np (a, (b, c)) * (e, (f, g)) = (a * e, (b, c) * (f, g)) = (a * e, (b * f, c * g)) //((a, b), c) % (d, (e, f)) = ((a, b) % d, c % (e, f)) = ((a % d, b % d), (c % e, c % f)) //Typ zwracanej pary jest wybierany na podstawie typów element operator element. np. // (int, long long) + (long long, unsigned int) = (long long, unsigned long long) // (bitset, int) >> (int, long long) = (bitset, long long) // (string, int) + (char *, double) = (string, double) #define f first #define s second #define vsv sim, class d, class e #define nop(o,c,r,l...) auto operator o(c a, r b)-> decltype(make_pair(l)) {return {l};} //enable_if jest potrzebne tylko, jeśli chcemy mieć operator <<, w przeciwnym wypadku można po prostu: vsv> nop ... #define pcg(o) \ /*para + para*/ vsv, class f> nop(o, pair , pair , a.f o b.f, a.s o b.s) \ /*liczba + para*/ vsv,class = typename enable_if::value>::type> nop(o, c, pair, a o b.f, a o b.s) \ /*para + liczba*/ vsv> nop(o, pair, e, a.f o b, a.s o b) #define clp(o) pcg(o) \ /*para += liczba*/ vsv> void operator o##= (pair & a, e b) {a.f o##= b; a.s o##= b;} \ /*liczba += para*/ vsv, class f> void operator o##= (pair & a, pair b) {a.f o##= b.f; a.s o##= b.s;} #define syd(o) sim, class d> auto operator o(pair e) -> decltype(make_pair(o e.f, o e.s)) {return {o e.f, o e.s};} #define u , //clp: razem z odpowiednim operatorem przypisania, pcg: bez niego, syd: operator jednoargumentowy clp(+) clp(-) clp(*) clp(/) clp(%) clp(^) clp(|) clp(>>) clp(<<) clp(&) pcg(&&) pcg(||) syd(-) syd(+) syd(~) syd(!) #undef u ll vec(pii a, pii b, pii c) { return vec(a - b, a - c); } ll sca(pii a, pii b) { return a.first * 1ll * b.first + a.second * 1ll * b.second; } int sign(ll x) { if (x > 0) return 1; if (x < 0) return -1; return 0; } int main() { int w, h, sx, sy, ex, ey; scanf("%d%d%d%d%d%d", &w, &h, &sx, &sy, &ex, &ey); pii start = {sy, sx}, end = {ey, ex}; if (start == end) { puts("0.00000000"); return 0; } vector board(h / 2, vi(w / 2)); for (int i = 0; i < h / 2; ++i) for (int j = 0; j < w / 2; ++j) scanf("%d", &board[i][j]); ld euk_dist = sqrt(K(sx - ex) + K(sy - ey)); debug imie(euk_dist); vpii on_path; map contact; auto get_height = [&](pii x) { return board[x.first][x.second]; }; for (int i = 0; i < h / 2; ++i) for (int j = 0; j < w / 2; ++j) { vpii points; for (int x = 0; x < 2; ++x) for (int y = 0; y < 2; ++y) points.emplace_back(2 * i + 2 * x, 2 * j + 2 * y); vi s; for (auto p : points) s.push_back(sign(vec(start, end, p))); debug imie(s) imie(points); if (s == vi(4, 1) || s == vi(4, -1)) continue; int m = *min_element(s.begin(), s.end()), M = *max_element(s.begin(), s.end()); if (m == -1 && M == 1) { on_path.emplace_back(i, j); } vpii zeros; for (int i = 0; i < 4; ++i) if (s[i] == 0) zeros.push_back(points[i]); //~ assert(zeros.size() == 1u); for (auto z : zeros) contact[z].emplace_back(i, j); } auto get_pos = [&](pii x) { x = 2 * x + 1; return sca(start - x, start - end); }; sort(on_path.begin(), on_path.end(), [&](pii x, pii y){return get_pos(x) < get_pos(y);}); ll vertical = 0; debug imie(on_path); int seen = 0; pii start_square = start / 2, end_square = end / 2; set actual_path; for (int i = 0; i + 1 < (int)on_path.size(); ++i) { if (on_path[i] == start_square) seen++; if (on_path[i] == end_square) seen++; int h1 = get_height(on_path[i]), h2 = get_height(on_path[i + 1]); debug imie(h1) imie(h2); if (seen == 1) { actual_path.insert(on_path[i]); actual_path.insert(on_path[i + 1]); vertical += abs(h1 - h2); } } ll extra = 0; for (auto [p, touching] : contact) { debug imie(p) imie(touching); if (touching.size() != 4u) continue; vpii on, off; for (auto p : touching) if (actual_path.count(p)) on.push_back(p); else off.push_back(p); if (on.size() == 2u) { vi which; for (auto x : touching) which.push_back(get_height(x)); sort(which.begin(), which.end()); int top = which[2]; int a = get_height(on[0]), b = get_height(on[1]); if (top > max(a, b)) extra += abs(top - a) + abs(top - b) - abs(a - b); } } debug imie(vertical) imie(extra); printf("%.10Lf\n", euk_dist + vertical + extra); }