#include #define mk std::make_pair #define st first #define nd second #define ll long long #define ld long double #define K long double using namespace std; std::vector > V; std::vector > visited; int W, H; ld A, B, C, D; int a, b; int c, d; const K EPS = 1e-9; struct xy { // punkt w 2D K x, y; xy(K xi, K yi):x(xi), y(yi) {} xy() {} K norm() const { return x*x+y*y; } // kwadrat(!) normy euklidesowej }; xy operator+(xy a, xy b) { return xy(a.x+b.x, a.y+b.y); } xy operator-(xy a, xy b) { return xy(a.x-b.x, a.y-b.y); } xy operator*(xy a, K f) { return xy(a.x*f, a.y*f); } xy operator/(xy a, K f) { return xy(a.x/f, a.y/f); } xy cross(xy a) { return xy(-a.y, a.x); } // obrot o 90 stopni K operator*(xy a, xy b) { return a.x*b.x+a.y*b.y; } K det(xy a, xy b) { return a.x*b.y-b.x*a.y; } // mowi czy jak bylismy w X, jestesmy w Y i bedziemy w Z to skrecamy w lewo(right-prawo) bool left(xy X, xy Y, xy Z) { return det(Y-X, Z-Y) > EPS; } bool right(xy X, xy Y, xy Z) { return det(Y-X, Z-Y) < -EPS;} struct xyz { // punkt w 3D K x, y, z; xyz(K xi, K yi, K zi):x(xi), y(yi), z(zi) {} xyz() {} K norm() const { return x*x+y*y+z*z; } // kwadrat(!) normy euklidesowej }; xyz normal; // UWAGA! ustaw ten wektor! xyz operator+(xyz a, xyz b) { return xyz(a.x+b.x, a.y+b.y, a.z+b.z); } xyz operator-(xyz a, xyz b) { return xyz(a.x-b.x, a.y-b.y, a.z-b.z); } xyz operator*(xyz a, K f) { return xyz(a.x*f, a.y*f, a.z*f); } xyz operator/(xyz a, K f) { return xyz(a.x/f, a.y/f, a.z/f); } // Iloczyn wektorowy. Uwaga: odwrotnie argumenty: cross(a,b)=bxa xyz cross(xyz a, xyz b=normal) { return xyz(b.y*a.z-a.y*b.z, b.z*a.x-a.z*b.x, b.x*a.y-a.x*b.y); } K operator*(xyz a, xyz b) { return a.x*b.x + a.y*b.y + a.z*b.z; } K det(xyz a, xyz b, xyz c=normal) { return cross(a, b) * c; } typedef xy P; struct segment { P a, b; }; // odcinek domkniety // Punkt p lezy na prostej zawierajacej s. Czy lezy na odcinku s? bool on_segment(P p, segment s) // (*) { return min(s.a.x, s.b.x) - p.x < EPS && p.x - max(s.a.x, s.b.x) < EPS && min(s.a.y, s.b.y) - p.y < EPS && p.y - max(s.a.y, s.b.y) < EPS; } // Czy dwa odcinki maja wspolny punkt? bool intersect(segment s1, segment s2) { std::cout << "Przeciecie: ((" << s1.a.x << ", " << s1.a.y << "), (" << s1.b.x << ", " << s1.b.y << "), (" << s2.a.x << ", " << s2.a.y << "), (" << s2.b.x << ", " << s2.b.y << "))\n"; K d1 = det(s2.b-s2.a, s1.a-s2.a), d2 = det(s2.b-s2.a, s1.b-s2.a), d3 = det(s1.b-s1.a, s2.a-s1.a), d4 = det(s1.b-s1.a, s2.b-s1.a); return (((d1>=EPS && d2<=-EPS) || (d1<=-EPS && d2>=EPS)) && ((d3>=EPS && d4<=-EPS) || (d3<=-EPS && d4>=EPS))) || (fabs(d1)> W >> H >> A >> B >> C >> D; B = H-B; D = H-D; std::vector tmp(W+5, 0); while (V.size() < H+5) V.push_back(tmp); std::vector tmp1(W+5, 0); while (visited.size() < H+5) visited.push_back(tmp1); for (int i = H/2; i >= 1; i--) for (int j = 1; j <= W/2; j++) std::cin >> V[j][i]; normal.x = normal.y = 0; normal.z = 1; } ld dfs(int x, int y, ld e) { std::cout << "jestem w (" << x << ", " << y << ")\n"; if (x == a && y == b) return e; visited[x][y] = true; int xx = x/2; int yy = y/2; P S = {c, d}; P E = {a, b}; std::cout << "S = (" << S.x << ", " << S.y << ")\n"; std::cout << "E = ( " << E.x << ", " << E.y << ")\n"; segment S1 = { S, E }; S1.a = S; S1.b = E; std::vector inter; P A, B; segment S2; // gora A.x = xx; A.y = yy+2; B.x = xx+2; B.y = yy+2; S2.a = A; S2.b = B; std::cout << "S1 = ((" << S1.a.x << ", " << S1.a.y << "), " << S1.b.x << ", " << S1.b.y << "))\n"; inter.push_back(intersect(S1, S2)); // prawo A.x = xx+2; A.y = yy+2; B.x = xx+2; B.y = yy; S2.a = A; S2.b = B; inter.push_back(intersect(S1, S2)); // dol A.x = xx; A.y = yy; B.x = xx+2; B.y = yy; S2.a = A; S2.b = B; inter.push_back(intersect(S1, S2)); // lewo A.x = xx; A.y = yy; B.x = xx; B.y = yy+2; S2.a = A; S2.b = B; inter.push_back(intersect(S1, S2)); int new_x, new_y; ld new_e = e; if (x < W && y < H && inter[0] && inter[1] && !visited[x+1][y+1]) { new_x = x+1; new_y = y+1; if (V[x+1][y] == V[x][y+1] && V[x+1][y] > V[x][y] && V[x+1][y+1] < V[x+1][y]) { new_e += V[x][y+1] - V[x][y]; new_e += V[x][y+1] - V[x+1][y+1]; } } else if (x < W && y > 1 && inter[1] && inter[2] && !visited[x+1][y-1]) { new_x = x+1; new_y = y-1; if (V[x+1][y] == V[x][y-1] && V[x+1][y] > V[x][y] && V[x+1][y-1] < V[x+1][y]) { new_e += V[x][y-1] - V[x][y]; new_e += V[x][y-1] - V[x+1][y-1]; } } else if (x >1 && y > 1 && inter[2] && inter[3] && !visited[x-1][y-1]) { new_x = x-1; new_y = y-1; if (V[x-1][y] == V[x][y-1] && V[x][y-1] > V[x][y] && V[x-1][y-1] < V[x][y-1]) { new_e += V[x][y-1] - V[x][y]; new_e += V[x][y-1] - V[x-1][y-1]; } } else if (x > 1 && y < H && inter[3] && inter[0] && !visited[x-1][y+1]) { new_x = x-1; new_y = y+1; if (V[x-1][y] == V[x][y+1] && V[x][y+1] > V[x][y] && V[x-1][y+1] < V[x][y+1]) { new_e += V[x][y+1] - V[x][y]; new_e += V[x][y+1] - V[x-1][y+1]; } } else if (y < H && inter[0] && !visited[x][y+1]) { new_x = x; new_y = y+1; } else if (x < W && inter[1] && !visited[x+1][y]) { new_x = x + 1; new_y = y; } else if (y > 1 && inter[2] && !visited[x][y-1]) { new_x = x; new_y = y-1; } else if (x > 1 && inter[3] && !visited[x-1][y]) { new_x = x-1; new_y = y; } if (e == new_e) { if (V[new_x][new_y] >= V[x][y]) new_e += V[new_x][new_y] - V[x][y]; else new_e += V[x][y] - V[new_x][new_y]; } return dfs(new_x, new_y, new_e); } void solve(){ input(); c = (A+1)/2; d = (B+1)/2; int x = (A+1)/2; int y = (B+1)/2; a = (C+1)/2; b = (D+1)/2; std::cout << "A = " << A << ", B = " << B << ", C = " << C << ", D = " << D << "\n"; std::cout << "c = " << c << ", d = " << d << "\n"; ld res = dfs(x, y, 0); ld dx = A - C; ld dy = B - D; std::cout << "dx = " << dx << ", dy = " << dy << "\n"; ld tmp = dx*dx + dy*dy; res += sqrtl(tmp); std::cout << std::setprecision(10) << std::fixed << res << "\n"; } int main() { std::ios_base::sync_with_stdio(0); std::cin.tie(nullptr); solve(); return 0; }