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;
  int64_t min_x=std::min(X(r1),X(r2));
  int64_t min_y=std::min(Y(r1),Y(r2));
  int64_t max_x=std::max(X(r1),X(r2));
  int64_t max_y=std::max(Y(r1),Y(r2));
  return X(p)>min_x&&X(p)<max_x&&Y(p)>min_y&&Y(p)<max_y;
}

point spiral(int i){
  if(i<=0)return{0,0};
  static std::vector<point>spiral{{0,0}};
  static 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;
    int64_t x=spiral[j].first;
    int64_t y=spiral[j].second;
    spiral.emplace_back(x+d*dx[j%4],y+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 MIN=[](int64_t a,int64_t b,int64_t c){return std::min(std::min(a,b),c);};
  auto MAX=[](int64_t a,int64_t b,int64_t c){return std::max(std::max(a,b),c);};
  return {
    {MIN(xs[0],xs[1],xs[2]),MIN(ys[0],ys[1],ys[2])},
    {MAX(xs[0],xs[1],xs[2]),MAX(ys[0],ys[1],ys[2])}
  };
}

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

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