kmjp's blog

競技プログラミング参加記です

TopCoder SRM 604 Div1 Hard FamilyCrest

SRM

Div1 Hardがノーヒントで解けたのは時初めてじゃなかろうか。
本番思いついたアプローチで正しかったしね。
ただ残念ながら本番は時間切れ。
http://community.topcoder.com/stat?c=problem_statement&pm=12921

問題

N個の線分で構成された図形が与えられる。
同じ図形を、大きさや向きを変えず位置だけずらしてコピーしていく。
コピーした図形同士は交差してはならない。

十分大きいが有限サイズの平面において、図形を無限にコピーすることは可能か答えよ。

解法

平面の大きさは有限なので、図形を広く敷き詰めても無限にコピーできない。
逆に、図形を極小サイズ(dx,dy)だけずらして配置することができれば、kを任意の実数として(k*dx,k*dy)ずらした図形を配置することができる。

よって、移動後に元の図形と重ならない(dx,dy)が存在するかどうかを調べればよい。
元図形の線分の対P,Qについて、移動前後で重なる条件は以下の通り。

  1. P,Qがもともと交差している場合、どちらに(dx,dy)動かしても交差する。
  2. P,Qがもともと交差していない場合、どちらに(dx,dy)動かしても(dx,dyが十分小さければ)交差しない。
  3. P,Qにおいて、片方の端点が片方の辺の上に乗っている場合、どちらに(dx,dy)動かしても交差する。
    • P,QがＴ字状になっている場合を考えると、Tを上側に動かすと移動後の縦棒が移動前の横棒と交差するし、Tを下側に動かしても移動後の縦棒が移動前の横棒と交差する。横に動かすのももちろんアウト。よってどちらにも動かせない。
  4. P,Qがもともと重なっている場合、線分の方向と異なる方向に動かせば交差しない。
  5. P,Qが片方の端点を共有している場合、角度によって交差する・しないが異なる。

上記判定で1～3は移動前後の交差の有無は移動する向きに依存しない。
また、4においては線分の方向とほんの少しだけずらした角度に動かせばよいので問題にならない。

のこる問題は、5のケースにおいて移動不可能な角度を列挙し、360度全包囲されていないかを確認することである。
5のケースにけるPとQの共有端点をa、P,Qのもう一つの点をb,cとする。
ベクトルabとacがなす角度が180度以下であるとする(180度を超えるなら、PとQを逆にする)。
するとatan(ab)～atan(ac)及び(atan(ab)+π)～(atan(ac)+π)の範囲に移動すると交差しない。
逆にatan(ac)～(atan(ab)+π)及び(atan(ac)+π)～atan(ab)の範囲は交差する。

上記手順で交差する移動角度の範囲を列挙できる。
あとはこれが360度をカバーするか調べればよい。
360度のカバー判定は、「移動角度の範囲」集合に登場する角度から２つを選び、その二等分線が「移動角度の範囲」に覆われないか判定することで行っている。

class FamilyCrest {
	int N;
	vector<int> X1,Y1,X2,Y2;
	set<pair<double,double> > S;
	public:
	
	int cross(int a,int b) {
		// par?
		int dx1=X2[a]-X1[a],dy1=Y2[a]-Y1[a];
		int dx2=X2[b]-X1[b],dy2=Y2[b]-Y1[b];
		if(dx1*dy2-dx2*dy1==0) return 0;
		
		// same point
		if(X1[a]==X1[b] && Y1[a]==Y1[b]) return 0;
		if(X2[a]==X1[b] && Y2[a]==Y1[b]) return 0;
		if(X1[a]==X2[b] && Y1[a]==Y2[b]) return 0;
		if(X2[a]==X2[b] && Y2[a]==Y2[b]) return 0;
		
		ll x11=X1[a],x12=X2[a],y11=Y1[a],y12=Y2[a];
		ll x21=X1[b],x22=X2[b],y21=Y1[b],y22=Y2[b];
		if(	((x12-x11)*(y21-y11)-(y12-y11)*(x21-x11))*
			((x12-x11)*(y22-y11)-(y12-y11)*(x22-x11)) <= 0) {
			if(((x11-x21)*(y22-y21)-(y11-y21)*(x22-x21))*
				((x12-x21)*(y22-y21)-(y12-y21)*(x22-x21)) <= 0) return 1;
		}
		return 0;
	}
	
	void addcand(int dx1,int dy1,int dx2,int dy2) {
		int g=__gcd(abs(dx1),abs(dy1));
		dx1/=g;dy1/=g;
		g=__gcd(abs(dx2),abs(dy2));
		dx2/=g;dy2/=g;
		
		if(dx1==dx2 && dy1==dy2) return;
		
		double d1=atan2(dy1,dx1);
		double d2=atan2(dy2,dx2);
		if(d1<0) d1+=atan(1)*8;
		if(d2<0) d2+=atan(1)*8;
		if(d2<d1) swap(d1,d2);
		if(d2-d1>=atan(1)*4) swap(d1,d2);
		double dif=d2-d1;
		
		double d3=d1+atan(1)*4;
		if(d3>=atan(1)*8) d3-=atan(1)*8;
		S.insert(make_pair(d2,d3));
		
		d3=d2+atan(1)*4;
		if(d3>=atan(1)*8) d3-=atan(1)*8;
		S.insert(make_pair(d3,d1));
	}
	
	string canBeInfinite(vector <int> A, vector <int> B, vector <int> C, vector <int> D) {
		int x,y,i;
		N=A.size();
		X1=A;Y1=B;X2=C;Y2=D;
		
		FOR(x,N) FOR(y,N) if(cross(x,y)) return "Finite";
		S.clear();
		FOR(x,N) FOR(y,N) {
			if(X1[x]==X1[y] && Y1[x]==Y1[y]) addcand(X2[x]-X1[x],Y2[x]-Y1[x],X2[y]-X1[y],Y2[y]-Y1[y]);
			if(X1[x]==X2[y] && Y1[x]==Y2[y]) addcand(X2[x]-X1[x],Y2[x]-Y1[x],X1[y]-X2[y],Y1[y]-Y2[y]);
			if(X2[x]==X1[y] && Y2[x]==Y1[y]) addcand(X1[x]-X2[x],Y1[x]-Y2[x],X2[y]-X1[y],Y2[y]-Y1[y]);
			if(X2[x]==X2[y] && Y2[x]==Y2[y]) addcand(X1[x]-X2[x],Y1[x]-Y2[x],X1[y]-X2[y],Y1[y]-Y2[y]);
		}
		
		if(S.empty()) return "Infinite";
		
		set<double> DD;
		ITR(it,S) DD.insert(it->first),DD.insert(it->second);
		vector<double> V=vector<double>(DD.begin(),DD.end());
		FOR(x,V.size()) FOR(y,V.size()) {
			double deg=(V[x]+V[y])/2;
			FOR(i,2) {
				int ng=0;
				
				ITR(it,S) {
					if(it->first<=it->second && deg>=it->first-1e-9 && deg<=it->second+1e-9) ng++;
					if(it->first>it->second && (deg>=it->first-1e-9 || deg<=it->second+1e-9)) ng++;
				}
				
				if(!ng) return "Infinite";
				
				deg+=atan(1)*4;
				if(deg>=atan(1)*8) deg-=atan(1)*8;
			}
		}
		
		return "Finite";
	}
};

まとめ

ノーヒントで解けたのはうれしい。
しかし本番でこのコード量を１発で通すのは難しすぎる…。