TopCoder SRM 500 Div1 Medium FractalPicture

またちょっと変わった問題。
http://community.topcoder.com/stat?c=problem_statement&pm=11344

問題

多数の線分で構成されたフラクタル図形の生成方法が与えられる。
２次元座標上の矩形領域が与えられたとき、その中に含まれるフラクタル図形の線分の長さの総和を求めよ。

解法

図形全部が矩形の中に入る場合、線分の総和は全部最終的な解答に含まれる。
フラクタル図形を再帰的にチェックして行けばよい。

• 図形が全く矩形に入らない → 解答に含まれる線分の長さは0
• 図形が全て矩形に入る → 解答に含まれる線分の長さは図形全部
• 図形が一部矩形に入る → 再帰的に各部分が矩形に含まれるかチェック

フラクタルは世代が進むたびに大きさが1/3になったり回転したりして計算がややこしいが、以下のコードでは図形でなく矩形を拡縮回転しコードの複雑さを軽減している。

double fin[502],totgen[502];

class FractalPicture {
	public:
	double gen(int g,int x1,int y1,int x2,int y2) {
		if(g==500) return 0;
		
		x1=max(-10000,min(x1,10000));
		x2=max(-10000,min(x2,10000));
		y1=max(-10000,min(y1,10000));
		y2=max(-10000,min(y2,10000));
		if(x2<-27 || x1>27) return 0;
		if(y2<0 || y1>81) return 0;
		if(x1<=-27 && x2>=27 && y1<=0 && y2>=81) return totgen[g];
		
		double ret=0;
		if(x1<=0 && x2>=0) ret += fin[g]*(max(0,min(y2,54))-min(54,max(y1,0)))/54.0;
		ret += gen(g+1,x1*3,(y1-54)*3,x2*3,(y2-54)*3);  //top
		ret += gen(g+1,(y1-54)*3,-x2*3,(y2-54)*3,-x1*3);//left
		ret += gen(g+1,(54-y2)*3,x1*3,(54-y1)*3,x2*3);//right
		
		return ret;
	}
	
	double getLength(int x1, int y1, int x2, int y2) {
		int i=0;
		fin[0]=54;
		FOR(i,500) fin[i+1]=fin[i]/3.0;
		totgen[499]=fin[499]*1.5;
		for(i=499;i>0;i--) totgen[i-1] = fin[i-1] + 3*totgen[i];
		
		return gen(0,x1,y1,x2,y2);
	}
};

まとめ

ややこしいけど面白かった問題。