TopCoder SRM 604 Div1 Hard FamilyCrest

問題

線分の（重複）集合からなる図形が(x1[i], y1[i]), (x2[i], y2[i])により与えられる。
この図形を平面上に回転させずに、ずらして、コピーする。
どの二つのコピーも重ならないように、平面内の有限の範囲に無限に敷き詰められるか否かを判定せよ。

制約条件

n≦50
座標の絶対値≦1万とか

方針

二つの線分だけに着目する。
二つの線分が、両方の端点以外の一点で交わっていたら明らかにFinite.

片方の線分をどの向きにずらしてはいけないかというのは簡単に求められる。
直感的に言うと、自分が相手に刺さる方向にはずらしてはいけない。
オーバーラップしているときは特別で、お互いの線分の向きにずらしてはいけない。
（上手くやればこのコーナーはいらなかったかもしれない）

で、全ての二線分の組み合わせについてダメな角度の範囲を求めたら、
累積和を使って、大丈夫な角度の範囲があるかどうかを見ればいい。

75分の時間内に解くのはきついけど、ICPCの幾何よりはだいぶ簡単。

ソースコード

map<double, int> m;
void add(double a, double b){
	if(b + EPS < a){
		add(a, PI);
		add(-PI, b);
		return;
	}
	a += PI; b += PI;
	m[a - EPS]++;
	m[b + EPS]--;
}
double angle(double a, double b){
	if(a > b + EPS) b += 2 * PI;
	return b - a;
}

class FamilyCrest {
	public:
	string canBeInfinite(vector <int> A, vector <int> B, vector <int> C, vector <int> D) {
		m.clear();
		int n = A.size();
		vector<L> ls;
		
		rep(i, n) ls.pb(L(P(A[i], B[i]), P(C[i], D[i])));
		rep(i, n) rep(j, n){
			if(!intersectSS(ls[i], ls[j])) continue; //交わってないやつは関係ない
			if(overlap(ls[i], ls[j])){
				double a = arg(ls[i][1] - ls[i][0]);
				add(a, a);
				continue;
			}
			P p = crosspoint(ls[i], ls[j]);
			int x = -1, y = -1;
			rep(k, 2) if(abs(ls[i][k] - p) < EPS) x = k;
			rep(k, 2) if(abs(ls[j][k] - p) < EPS) y = k;
			if(x < 0 || y < 0) return "Finite"; //端点以外で交わっている
			
			double a = arg(ls[i][x] - ls[i][1 - x]);
			double b = arg(ls[j][1 - y] - ls[j][y]);
			if(angle(a, b) > PI + EPS) swap(a, b); //鋭角の範囲だけ
			//cerr<<"i: "<<i<<" j: "<<j<<" a: "<<a/PI*180<<" b: "<<b/PI*180<<endl;
			add(a, b);
		}
		
		m[0] = m[2*PI] = 0;
		int cnt = 0;
		each(i, m){
			cnt += i->second;
			if(0 <= i->first && i->first <= 2 * PI && cnt == 0) return "Infinite"; //大丈夫な角度があった
		}
		return "Finite";
	}
};