Codeforces #283 Div1 D. Gears

整理すると意外と簡単。
http://codeforces.com/contest/497/problem/D

問題

２次元座標上で、２つの多角形A,Bを構成するN,M個の点の座標が与えられる。
初期状態でAとBは交差していない。
多角形Aは点Pの周りを、多角形Bは点Qの周りを同じ角速度で回る。

AとBが交差することはあるか答えよ。

解法

多角形同士が交差するのは、A中のどれかの点がB中のどれかの辺を横断するか、逆にB中のどれかの点がA中のどれかの辺を横断する場合である。
よって両多角形の点・辺の対においてこれらを判定すれば、O(NM)で解ける。

問題は片方の点が片方の辺を横断するかの判定である。
例えばB中の点がA中の辺を横断するか判定することを考える。

AとBが同時に動くと処理が難しいので、Aが固定されるような座標系に変換する。
まずPが原点Oに来るよう、全体を平行移動する。

回転に対し、全体がθ回転してもAの座標が変わらないようにするには、Bの点をQの周りにθ回転させた後原点Oの周りに-θ回転させて戻せばよい。

この時のBの点の座標を考える。
Pが原点Oに平行移動後の座標において、Bの点(x,y)が点Q(a,b)を中心にθ回転した後の座標(x', y')はとすると
となる。
この(x', y')を原点を中心に-θ回転させた点(x'', y'')は
となる。
すなわち、(x'',y'')は中心を(x-a,y-b)とする半径の円上に乗る。

この点(x'',y'')がAの辺を横断するのであれば、Aの辺を構成する各線分のいずれかがこの円と交差することになる。
よってAの各線分について円の中心(x-a,y-b)からの最短距離・最大距離を求め、この距離がを挟むか判定すればよい。

int N,M;
ll CX1,CY1,CX2,CY2;
int X[2][1010],Y[2][1010];

bool hit() {
	int i,j;
	FOR(i,N) {
		FOR(j,M) {
			ll cx=X[1][j]-CX2;
			ll cy=Y[1][j]-CY2;
			ll r=CX2*CX2+CY2*CY2;
			ll r1=(X[0][i]-cx)*(X[0][i]-cx)+(Y[0][i]-cy)*(Y[0][i]-cy);
			ll r2=(X[0][(i+1)%N]-cx)*(X[0][(i+1)%N]-cx)+(Y[0][(i+1)%N]-cy)*(Y[0][(i+1)%N]-cy);
			double ma=max(r1,r2);
			double mi=min(r1,r2);
			
			// min dist in segment
			double dx=X[0][(i+1)%N]-X[0][i];
			double dy=Y[0][(i+1)%N]-Y[0][i];
			double nor=sqrt(dx*dx+dy*dy);
			dx/=nor;
			dy/=nor;
			double rr=dx*(cx-X[0][i])+dy*(cy-Y[0][i]);
			if(rr>=-1e-9 && rr<=nor+1e-9) {
				dx=rr*dx+X[0][i];
				dy=rr*dy+Y[0][i];
				mi=min(mi,(dx-cx)*(dx-cx)+(dy-cy)*(dy-cy)-1e-10);
			}
			
			if(mi<=r && r<=ma) return true;
		}
	}
	return false;
	
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>CX1>>CY1>>N;
	FOR(j,N) cin>>X[0][j]>>Y[0][j], X[0][j]-=CX1,Y[0][j]-=CY1;
	cin>>CX2>>CY2>>M;
	FOR(j,M) cin>>X[1][j]>>Y[1][j], X[1][j]-=CX1,Y[1][j]-=CY1;
	CX2-=CX1, CY2-=CY1;
	
	if(hit()) return _P("YES\n");
	swap(N,M);
	FOR(j,1002) swap(X[0][j],X[1][j]), X[0][j]-=CX2, X[1][j]-=CX2;
	FOR(j,1002) swap(Y[0][j],Y[1][j]), Y[0][j]-=CY2, Y[1][j]-=CY2;
	CX2=-CX2,CY2=-CY2;
	if(hit()) return _P("YES\n");
	
	_P("NO\n");
}

まとめ

「Qを中心に回転させた結果は、Aから相対的に見た座標系においても円を描く」ということを知ってる/気づくことができればどうにかなる。
自分は本番気づかなかったのでどうにもならなかったけどね。