Invasion zombie v1

invasion_zombiev1.cpp

const int MAX       = 1000;
//endregion
long long X, Y, N;
 
long long ta(long long length)
{
    return length * (length + 1) / 2;
}
 
// Upper right
long long upperRightArea(long long length, long long x, long long y)
{
    long long t = ta(length);
    long long u = N - y + 1;
    long long r = N - x + 1;
    long long lu = min(u, length);
    long long lr = min(r, length);
 
    long long su = ta(max(0ll, length - u));
    long long sr = ta(max(0ll, length - r));
    long long ix = x + lr;
    long long iy = y + lu;
 
    long long h = length - (ix - x);
    long long w = length - (iy - y);
    long long over = ta(min(max(h - lu, 0ll), max(w - lr, 0ll)));
 
    return t - su - sr + over;
}
 
// Rotate 90 degrees clockwise
pair<long long, long long> rotate(pair<long long, long long> p)
{
    long long xx = p.second;
    long long yy = N - p.first + 1;
    return make_pair(xx, yy);
}
 
long long area(long long length)
{
    if (length == 0) { return 0; }
    pair<long long, long long> p(X, Y);
    long long ur = upperRightArea(length, p.first, p.second);
 
    p = rotate(p);
    long long ul = upperRightArea(length, p.first, p.second);
 
    p = rotate(p);
    long long dl = upperRightArea(length, p.first, p.second);
 
    p = rotate(p);
    long long dr = upperRightArea(length, p.first, p.second);
 
    long long u = min(length, N - Y + 1);
    long long r = min(length, N - X + 1);
    long long d = min(length, Y);
    long long l = min(length, X);
    long long a = ur + ul + dl + dr - u - r - d - l + 1;
 
    return a;
}
 
 
int main(int argc, char **argv)
{
    long long C;
    scanf("%lld %lld %lld %lld", &N, &X, &Y, &C);
    long long low = 0, high = N + N + 1, mid;
    while (low < high) {
        mid = (low + high) / 2;
        long a = area(mid);
        if (a < C) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
 
    printf("%lld", low - 1);
    return EXIT_SUCCESS;
}