Labyrintti

#include <stdint.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <vector>

typedef std::pair<int64_t,int64_t>point;

inline int64_t& X(point& p){return p.first;}
inline int64_t& Y(point& p){return p.second;}

bool within(point p,std::pair<point,point>bounds){
  auto r1=bounds.first,r2=bounds.second;
  return X(p)>std::min(X(r1),X(r2))&&X(p)<std::max(X(r1),X(r2))&&
         Y(p)>std::min(Y(r1),Y(r2))&&Y(p)<std::max(Y(r1),Y(r2));
}

point spiral(int i){
  if(i<=0)return{0,0};
  static std::vector<point>spiral{{0,0}};
  static const std::vector<int>dx{1,0,-1,0},dy{0,-1,0,1};
  for(int j=spiral.size()-1;j<i;++j){
    int64_t d=2ULL<<j;
    spiral.emplace_back(
	X(spiral[j])+d*dx[j%4],
	Y(spiral[j])+d*dy[j%4]);
  }
  return spiral[i];
}

std::pair<point,point>box(int i){
  point p[3]{spiral(i),spiral(i-1),spiral(i-4)};
  int64_t xs[3]{X(p[0]),X(p[1]),X(p[2])};
  int64_t ys[3]{Y(p[0]),Y(p[1]),Y(p[2])};
  auto min3=[](int64_t a[]){return std::min(std::min(a[0],a[1]),a[2]);};
  auto max3=[](int64_t a[]){return std::max(std::max(a[0],a[1]),a[2]);};
  return {{min3(xs),min3(ys)},{max3(xs),max3(ys)}};
}

point corner(int i){
  static const std::vector<int>dx{-1,1,1,-1},dy{1,1,-1,-1};
  auto p=spiral(i-4);
  return{X(p)+dx[i%4],Y(p)+dy[i%4]};
}

int64_t manhattan(point a,point b){
  return ::llabs(X(a)-X(b))+::llabs(Y(a)-Y(b));
}

int main(){
  point A,B;std::cin>>Y(A)>>X(A)>>Y(B)>>X(B);
  int64_t distance=0;
  bool foundA=false;
  for(int i=3;;++i){
    auto b=box(i);
    if(within(A,b)&&within(B,b))return std::cout<<manhattan(A,B)<<'\n',0;
    if(foundA){
      if(within(B,b))return std::cout<<distance+manhattan(B,corner(i-1))<<'\n',0;
      distance+=manhattan(corner(i-1),corner(i));
    }
    else{
      if(within(B,b))std::swap(A,B);
      if(within(A,b)){
	foundA=true;
	distance=manhattan(A,corner(i));
      }
    }
  }
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 2

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: ACCEPTED

Test 12

Group: 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 3

Verdict: ACCEPTED