Good Bye 2013 : E. New Year Tree Decorations

幾何だから敬遠されてるけど、特にヒネリもない問題。
http://codeforces.com/contest/379/problem/E

問題

N個の面グラフが重なっている。
各面グラフiに対し、各整数X座標におけるY座標Y[i][x]が与えられている。
各面グラフが占める面積を求めよ。

解法

各X座標(x～x+1)の範囲はそれぞれ独立に処理できる。
初期状態は(x,0)-(x+1,0)に線分があるとして、一番手前のグラフから順に(x,Y[i][x])-(x+1,Y[i][x+1])の線分を配置していく。
これまで置いた線分群のうち最もY座標を大きいものをmapで管理し、(x,Y[i][x])-(x+1,Y[i][x+1])-(x,0)-(x+1,0)の台形から、前記すでに配置した面グラフの占める面積を引けばよい。

ちまちま線分の交点を求めていくので面倒だけど、それだけ。

int N,K;
double Y[301][301];
double S[301];

void solve() {
	int f,i,j,k,l,x,y;
	cin>>N>>K;
	FOR(i,N) FOR(x,K+1) cin>>Y[i][x];
	
	FOR(x,K) {
		map<double,double> M;
		M[0]=0;
		M[1]=0;
		FOR(i,N) {
			map<double,double> M2;
			M2[0]=M[0];
			double prex=0,prey=M[0];
			ITR(it,M) {
				if(it->first==0) continue;
				double cx = it->first;
				double cy = it->second;
				double y1= Y[i][x]+(Y[i][x+1]-Y[i][x])*prex;
				double y2= Y[i][x]+(Y[i][x+1]-Y[i][x])*cx;
				
				
				if(y1>=prey && y2>=cy) {
					S[i] += ((y1+y2)-(cy+prey))*(cx-prex)/2.0;
					M2[cx]=y2;
				}
				else if(y1<=prey && y2<=cy) {
					M2[cx]=cy;
				}
				else if(y1>=prey && y2<=cy) {
					double nx = prex + (cx-prex)*(abs(y1-prey)/(abs(y1-prey)+abs(y2-cy)));
					double ny = prey + (cy-prey)*(abs(y1-prey)/(abs(y1-prey)+abs(y2-cy)));
					
					S[i] += ((y1-prey))*(nx-prex)/2.0;
					M2[nx]=ny;
					M2[cx]=cy;
				}
				else if(y1<=prey && y2>=cy) {
					double nx = prex + (cx-prex)*(abs(y1-prey)/(abs(y1-prey)+abs(y2-cy)));
					double ny = prey + (cy-prey)*(abs(y1-prey)/(abs(y1-prey)+abs(y2-cy)));
					
					S[i] += ((y2-cy))*(cx-nx)/2.0;
					M2[nx]=ny;
				}
				prex = cx; prey= cy;
			}
			M2[0]=max(M2[0],Y[i][x]);
			M2[1]=max(M2[1],Y[i][x+1]);
			swap(M,M2);
			
		}
	}
	
	FOR(i,N) _P("%.12lf\n",S[i]);
	
}

まとめ

本番こっち解けばよかった…。