天下一プログラマーコンテスト2014 予選A : D - EMLauncher

本番しょうもないバグで時間を使い果たした。
http://tenka1-2014-quala.contest.atcoder.jp/tasks/tenka1_2014_qualA_d

問題

２次元座標上にN個の線分が与えられる。
これら線分は互いに共通部分を持たず、また原点を通らない。

ここで、原点から何本か半直線を引き、各線分が最低１個以上の半直線と交わるまたは接するようにしたい。
引くべき半直線を最小化せよ。

解法

似た問題は蟻本にも登場している。
ただし蟻本では一直線に伸びる時間軸の上でタスクが存在する、というような問題だったが、今回は角度で考えると0度と360度が連結しているのがちょっと厄介。

半直線と線分が交わるかどうかは、線分の両端の座標を円座標で考えたとき、動径は関係なく２点の偏角の間に半直線の偏角が含まれるかどうかで決まる。
そこで、まず各線分の端点を円座標にした時の偏角を求め、また偏角が小さいほうを始点、大きいほうを終点とするように並べ替えておく。

偏角を求める際atanを使うとマイナスの値が出ることもあるが、面倒なので以下では偏角は正の値にそろえておく。
ここで、半直線を引く角度の候補はいずれかの始点の偏角だけでよいことに注目する。

よってまず最初の１本の半直線を、N個の線分の始点で総当たりする。
総当たりの各ループにおいて、最初の１本の半直線と交わらない残りの線分を、左回りに偏角を求めて引くべき最小の半直線数を求めていく。
この手順は蟻本の区間スケジューリングに近く、事前のソートを合わせてO(N*logN)で解ける。
１本目の半直線の選び方と合わせて、全体でO(N^2*logN)。

小数演算が多いので誤差に注意。

int N;
int X1[2003],Y1[2003],X2[2003],Y2[2003],X3[2003],Y3[2003];
double D1[2003],D2[2003];
double PI2=atan(1)*8;
double EPS=1e-9;
 
void solve() {
	int f,i,j,k,l,x,y;
	cin>>N;
	FOR(i,N) {
		cin>>X1[i]>>Y1[i]>>X2[i]>>Y2[i];
		
		X3[i]=(X1[i]+X2[i]);
		Y3[i]=(Y1[i]+Y2[i]);
		x=__gcd(abs(X1[i]),abs(Y1[i]));
		y=__gcd(abs(X2[i]),abs(Y2[i]));
		D1[i]=atan2(Y1[i]/x,X1[i]/x);
		D2[i]=atan2(Y2[i]/y,X2[i]/y);
		
		if(X1[i]*Y3[i]-Y1[i]*X3[i]<0) swap(D1[i],D2[i]);
		D1[i]-=EPS;
		D2[i]+=EPS;
 
		if(D1[i]<0) D1[i]+=PI2;
		while(D2[i]<D1[i]) D2[i]+=PI2;
	}
	int ret=N;
	FOR(i,N) {
		double xx=D2[i]-EPS;
		vector<pair<double,double> > P;
		FOR(j,N) {
			if(D1[j]<=xx && xx<=D2[j]) continue;
			if(D1[j]<=xx+PI2 && xx+PI2<=D2[j]) continue;
			if(xx<D1[j]) P.push_back(make_pair(D2[j],D1[j]));
			if(D2[j]<xx) P.push_back(make_pair(D2[j]+PI2,D1[j]+PI2));
		}
		if(P.empty()) return _P("1\n");
		sort(P.begin(),P.end());
		
		int num=1;
		x=y=0;
		while(x<P.size()) {
			while(y<P.size() && P[y].second<=P[x].first) y++;
			num++;
			x=y;
		}
		ret=min(num,ret);
	}
	cout<<ret<<endl;
}

まとめ

アルゴリズムはすぐに思い浮かんだけど、時間内にきっちりくみ切れなかったのが残念。