Invasion zombie v2

invasion_zombiev2.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long           int64;
 
inline int64 f(int64 x) {
    return x * x + (x + 1) * (x + 1);
}
 
inline int64 g(int64 x) {
    return x * (x + 1) / 2;
}
 
bool check(int64 d, int64 n, int64 x, int64 y, int64 c) {
    int64 upper_height  = max(0ll, d - (n - (y + 1)));
    int64 right_height  = max(0ll, d - (n - (x + 1)));
    int64 bottom_height = max(0ll, d - y);
    int64 left_height   = max(0ll, d - x);
 
    int64 upper_area = upper_height * upper_height;
    int64 right_area = right_height * right_height;
    int64 left_area  = left_height  * left_height;
    int64 bottom_area = bottom_height * bottom_height;
    int64 center = f(d) - left_area - right_area - upper_area - bottom_area;
 
    int64 nw = max(0ll, upper_height - (x + 1));
    int64 ne = max(0ll, upper_height - (n - x));
    int64 se = max(0ll, bottom_height - (n - x));
    int64 sw = max(0ll, bottom_height - (x + 1));
    center += g(nw) + g(ne) + g(se) + g(sw);
    return center >= c;
}
 
int main() {
    int64 n, x, y, c;
    cin >> n >> x >> y >> c;
    x--;
    y--;
    int64 low = 0, high = n + n + 1;
    while (low < high) {
        int64 mid = low + (high - low) / 2;
        if (check(mid, n, x, y, c)) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    cout << low << endl;
    return EXIT_SUCCESS;
}