SRM500 Div1 Medium(500) FractalPicture

FractalPicture

長さがLのnon-finalな線分に問題の操作をk回行うと、線分の総延長は(1+2k/3)Lになる。x1,y1,x2,y2は全て整数なので線分の長さが1になるまで調べれば、以降は、あるnon-finalな線分から生成される図形は全てRに含まれるか全て含まれないかのいずれか。

#include <algorithm>
#define y1 y1_
using namespace std;

int x1, y1, x2, y2;
int horizontal( int y, int A, int B );

int vertical( int x, int A, int B )
{
    int l = 0;

    if ( abs(A-B) == 1 )
    {
        if ( y1<=min(A,B) && max(A,B)<=y2 )
        {
            if ( x1<=x   && x  <=x2 )  l += 1;
            if ( x1<=x-1 && x  <=x2 )  l += 495/3;
            if ( x1<=x   && x+1<=x2 )  l += 495/3;
        }
    }
    else
    {
        int C = (2*B+A)/3;

        if ( x1<=x && x<=x2 )
            l += max( 0, min(y2,max(A,C))-max(y1,min(A,C)) );
        l += horizontal(C,x,x-(A-B)/3);
        l += vertical(x,C,B);
        l += horizontal(C,x,x+(A-B)/3);
    }

    return l;
}

int horizontal( int y, int A, int B )
{
    int l = 0;

    if ( abs(A-B) == 1 )
    {
        if ( x1<=min(A,B) && max(A,B)<=x2 )
        {
            if ( y1<=y   && y  <=y2 )  l += 1;
            if ( y1<=y-1 && y  <=y2 )  l += 495/3;
            if ( y1<=y   && y+1<=y2 )  l += 495/3;
        }
    }
    else
    {
        int C = (2*B+A)/3;

        if ( y1<=y && y<=y2 )
            l += max( 0, min(x2,max(A,C))-max(x1,min(A,C)) );
        l += vertical(C,y,y-(A-B)/3);
        l += horizontal(y,C,B);
        l += vertical(C,y,y+(A-B)/3);
    }

    return l;
}

class FractalPicture{public:
double getLength( int x1, int y1, int x2, int y2 )
{
    ::x1=x1, ::y1=y1, ::x2=x2, ::y2=y2;
    return vertical(0,0,81);
}};