Cod sursa(job #1036552)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 19 noiembrie 2013 14:32:37
Problema Fractal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.52 kb
#include <fstream>
using namespace std;
ifstream fin("fractal.in");
ofstream fout("fractal.out");
int state[4] = {0,1,2,3},ans,midx,midy,newx1,newx2,newy1,newy2,x,y,k;
void flip_left ()
{
    int temp = state[0];
    for (int i=0; i<3; ++i)
    {
        state[i] = state[i+1];
    }
    state[3] = temp;

}
void flip_right ()
{
    int temp = state[3];
    for (int i=3; i>=1; --i)
    {
        state[i] = state[i-1];
    }
    state[0] = temp;
}
bool check (int i, int x1, int x2, int y1, int y2)
{
    if (i==0)
    {
        newx1 = x1; newx2 = midx; newy1 = y1; newy2 = midy;
        return (x1<=x && x <= midx && y1 <=y && y<=midy);
    }
    else if (i==1)
    {
        newx1 = x1; newx2 = midx; newy1 = midy+1; newy2 = y2;
        return (x1<=x && x <= midx && midy < y && y <=y2);
    }
    else if (i==2)
    {
        newx1 = midx+1; newx2 = x2; newy1 = midy+1; newy2 = y2;
        return (midx<x && x <= x2 && midy < y && y <=y2);
    }
    else
    {
        newx1 = midx+1; newx2 = x2; newy1 = y1; newy2 = midy;
        return (midx<x && x <= x2 && y1 <=y && y<=midy);
    }
}

void SW ()
{
    swap (state[0],state[3]);
    swap (state[1],state[2]);
}

void divide (int x1, int x2, int y1, int y2, int clockwise)
{
    if (x1==x2) return;
    midx = (x1+x2)/2;
    midy = (y1+y2)/2;
    int add = (midx-x1+1)*(midx-x1+1);

    if (clockwise)
    {
        SW();
    }

    if (check(state[0],x1,x2,y1,y2))
    {
        if (!clockwise)
        {
            flip_left ();
            divide (newx1,newx2,newy1,newy2,1-clockwise);
        }
        else
        {
            SW();
            flip_right ();
            divide (newx1,newx2,newy1,newy2,1-clockwise);
        }
        return;
    }
    else ans += add;
    if (check(state[1],x1,x2,y1,y2))
    {
        if (clockwise) SW();
        divide (newx1,newx2,newy1,newy2,clockwise);
        return;
    }
    else ans += add;
    if (check(state[2],x1,x2,y1,y2))
    {
        if (clockwise) SW();
        divide (newx1,newx2,newy1,newy2,clockwise);
        return;
    }
    else ans += add;
    if (check(state[3],x1,x2,y1,y2))
    {
        if (!clockwise)
        {
            flip_right ();
            divide (newx1,newx2,newy1,newy2,1-clockwise);
        }
        else
        {
            SW();
            flip_left ();
            divide (newx1,newx2,newy1,newy2,1-clockwise);
        }
    }
}
int main()
{
    fin>>k>>x>>y;
    divide (1,1<<k,1,1<<k,0);
    fout<<ans;
}