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 a=bounds.first,b=bounds.second;
  return X(p)>std::min(X(a),X(b))&&X(p)<std::max(X(a),X(b))&&
         Y(p)>std::min(Y(a),Y(b))&&Y(p)<std::max(Y(a),Y(b));
}

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

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

point corner(int i){
  static 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