Codeforces #172 Div1. A. Rectangle Puzzle

さてこの問題は本番に解けたもの。
http://codeforces.com/contest/280/problem/A

問題

長方形の幅と高さ、そして回転角が与えられる。
与えられた大きさの長方形と、その重心を中心として回転角分回転した長方形の共通部分を求めよ。

解法

色々解法があるが、ここでは元の長方形と回転後の長方形の辺の交点を求め、それらで囲まれる面積を求めた。
面積の求め方は、各交点から中心に対して辺を張ることで１点が原点にくる三角形がいくつも作れるので、後はベクトルの外積で求めるだけ。

int W,H,A;
double PX[4],PY[4];
double RX[4],RY[4];

vector<pair<double, pair<double,double> > > LI;

pair<double,double> cross(int p, int r) {
	double rx[2],ry[2];
	rx[0]=RX[r];
	ry[0]=RY[r];
	rx[1]=RX[(r+1)%4];
	ry[1]=RY[(r+1)%4];
	
	if(p==0 || p==2) {
		if(rx[1]<rx[0]) {
			swap(rx[0],rx[1]);
			swap(ry[0],ry[1]);
		}
		
		if(rx[1]<PX[p] || rx[0]>PX[p]) return make_pair(0.0,0.0);
		double YY=ry[1]+(ry[0]-ry[1])*(rx[1]-PX[p])/(rx[1]-rx[0]);
		if(YY>H/2.0 || YY<-H/2.0) return make_pair(0.0,0.0);;
		return make_pair(PX[p],YY);
	}
	else {
		if(ry[1]>ry[0]) {
			swap(rx[0],rx[1]);
			swap(ry[0],ry[1]);
		}
		
		if(ry[1]>PY[p] || ry[0]<PY[p]) return make_pair(0.0,0.0);
		double XX=rx[1]+(rx[0]-rx[1])*(ry[1]-PY[p])/(ry[1]-ry[0]);
		if(XX>W/2.0 || XX<-W/2.0) return make_pair(0.0,0.0);
		return make_pair(XX,PY[p]);
	}
	
}

void solve() {
	int f,r,i,j,k,l, x,y,ma,num,nt;
	
	GET3(&W,&H,&A);
	if(W<H) swap(W,H);
	if(A==0 || A==180) {
		_P("%.12f\n",W*(double)H);
		return;
	}
	if(A==90) {
		_P("%.12f\n",min(W,H)*(double)min(W,H));
		return;
	}
	
	if(A>90) A=180-A;
	
	
	double si=sin(A/180.0*(atan(1)*4));
	double co=cos(A/180.0*(atan(1)*4));
	PX[0]=W/2.0;
	PY[0]=H/2.0;
	PX[1]=W/2.0;
	PY[1]=-H/2.0;
	PX[2]=-W/2.0;
	PY[2]=-H/2.0;
	PX[3]=-W/2.0;
	PY[3]=H/2.0;
	
	FOR(i,4) {
		RX[i]=PX[i]*co-PY[i]*si;
		RY[i]=PX[i]*si+PY[i]*co;
	}
	
	FOR(x,4) FOR(y,4) {
		pair<double, double> pp = cross(x,y);
		
		if(pp.first==0 && pp.second==0) continue;
		LI.push_back(make_pair(atan2(pp.first,pp.second),pp));
	}
	
	sort(LI.begin(),LI.end());
	double SS=0;
	FOR(i,LI.size()) {
		SS += LI[i].second.first * LI[(i+1)%LI.size()].second.second - 
		LI[i].second.second * LI[(i+1)%LI.size()].second.first;
	}
	_P("%.12lf\n",-SS/2);
	
	return;
}

まとめ

今回は開店前の長方形はXY軸に平行、という仮定を置いたので交点の計算がラク。
うーん、ここらへんは幾何ライブラリをちゃんと揃えておくべきかな…。