【题目链接】:http://codeforces.com/problemset/problem/255/D

【题意】



给你一个n*n的方框;

给你一个方块;(以下说的方块都是单位方块)

每一秒钟,可以沿着当前有方块的地方往4个方向扩展一个方块;

问你最少要多少秒钟,平面上会有c个方块;

【题解】



画几张图可以发现,图形都是类似一个十字架的几何图案;

设a[n]表示第n-1秒时有多少个方块;

则有a[n] = a[n-1]+n*4

(a[1]=1)

递推一下能求出

a[n] = 2∗n 2 −2∗n+1 

但是可能会有一部分超出了格子的边界;

需要减去;超过的部分;

先求出这个图案的最左和最上、下、右的坐标;

看它在这4个方向上超过了多少;

减掉那个阶梯一样的部分;

因为4个方向都减掉了;

可能会有重复减掉的部分;

需要再加上;

不难发现;

设上半部分超过的部分为t

则如果y+t-1>n则右边和上边会有重复减掉的

如果y-(t-1)<1则左边和上边会有重复减掉的部分;

是一个阶梯(公差为1的等差数列);

….

下面和左边、右边重复的部分类似.

显然有单调性；

二分一下时间就好;



【Number Of WA】



0



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define ms(x,y) memset(x,y,sizeof x)

#define Open() freopen("D:\\rush.txt","r",stdin)

#define Close() ios::sync_with_stdio(0),cin.tie(0)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const int N = 310;

LL n,x,y,c;

LL sqr(LL x){ return x*x;}

int main(){

    //Open();

    Close();//scanf,puts,printf not use

    //init??????

    cin >> n >> x >> y >> c;

    LL L = 0,R = 1e5,ans = -1;

    while (L <= R){

        LL mid = (L+R)>>1;

        //mid = 2;

        LL temp = 2*sqr(mid+1)-2*(mid+1)+1;

        if (temp<c){

            L = mid + 1;

            continue;

        }

        LL r = x + mid,l = x - mid,u = y + mid,d = y - mid;

        if (r > n)

            temp-=1LL*(r-n)*(r-n);

        if (l < 1)

            temp-=1LL*(1-l)*(1-l);

        if (u > n){

            temp-=sqr(u-n);

            LL t = u-n;

            t--;

            if (x+t>n){

                temp+=(x+t-n+1)*(x+t-n)/2;

            }

            if (x-t<1){

                temp+=(1-x+t)*(1-x+t+1)/2;

            }

        }

        if (d < 1){

            temp-=sqr(1-d);

            LL t = 1-d;

            t--;

            if(x+t>n){

                temp+=(x+t-n+1)*(x+t-n)/2;

            }

            if(x-t<1){

                temp+=(1-x+t)*(1-x+t+1)/2;

            }

        }

       //         cout << temp << endl;

        //return 0;

        //cout <<mid<<"->"<<temp<<endl;

        //cout << endl;

        if (temp>=c){

            ans = mid;

            R = mid-1;

        }

        else

            L = mid+1;

    }

    cout << ans << endl;

    return 0;

}