Labyrintti

input/code.cpp: In function 'rect getSectorBounds(int)':
input/code.cpp:29:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

#include <iostream>
#include <vector>

using namespace std;
typedef long long int ll;

struct rect {
	ll x1, y1, x2, y2;
	rect(ll a, ll b, ll c, ll d) :x1(a), y1(b), x2(c), y2(d) {}
};

vector<ll> bounds;

ll pow2(int i) {
	return 1ll << i;
}
rect getSectorBounds(int i) {
	switch (i % 4) {
	case 0:
		return rect(bounds[i+1], bounds[i+4]+1, bounds[i+3]-1,bounds[i]-1);
	case 1:
		return rect(bounds[i + 4] + 1, bounds[i + 3] + 1, bounds[i] - 1, bounds[i+1]);
	case 2:
		return rect(bounds[i + 3] + 1, bounds[i] + 1, bounds[i + 1], bounds[i + 4] - 1);
	case 3:
		return rect(bounds[i] + 1, bounds[i + 1], bounds[i + 4] - 1, bounds[i + 3] - 1);
	}
	//return rect(0, 0, 0, 0);
}

int getSector(ll x, ll y) {
	for (int i = 0; ; i++) {
		rect r = getSectorBounds(i);
		if (r.x1 <= x && x <= r.x2 && r.y1 <= y && y <= r.y2)
			return i;
	}
}

int main() {
	bounds.push_back(0);
	bounds.push_back(0);
	bounds.push_back(0);
	bounds.push_back(2);
	for (int i = 4; i < 60;) {
		bounds.push_back(bounds[i - 2] - pow2(i-2)); i++;
		bounds.push_back(bounds[i - 2] - pow2(i-2)); i++;
		bounds.push_back(bounds[i - 2] + pow2(i-2)); i++;
		bounds.push_back(bounds[i - 2] + pow2(i-2)); i++;
	}

	ll x1, y1, x2, y2;
	cin >> y1 >> x1 >> y2 >> x2;
	if (getSector(x1, y1) > getSector(x2, y2)) {
		swap(x1, x2);
		swap(y1, y2);
	}


	ll res = 0;
	while (getSector(x1, y1) != getSector(x2, y2)) {
		int s = getSector(x1, y1);
		rect b = getSectorBounds(s);

		switch (s%4) {
		case 0:
			res += x1 - b.x1 + 1;
			x1 = b.x1 - 1;
			break;
		case 1:
			res += b.y2 - y1 + 1;
			y1 = b.y2 + 1;
			break;
		case 2:
			res += b.x2 - x1 + 1;
			x1 = b.x2 + 1;
			break;
		case 3:
			res += y1 - b.y1 + 1;
			y1 = b.y1 - 1;
			break;
		}
	}

	res += abs(x1 - x2) + abs(y1 - y2);
	cout << res;
}

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