SRM500 Div1 Medium(500) 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); }};