2015-2016 ACM-ICPC NEERC : D. Boulevard

ポカミスで手こずった。
http://codeforces.com/contest/589/problem/D

問題

１次元の数直線上をN人が歩いている。
各人は時刻T[i]に突如数直線上座標S[i]に現れ、座標F[i]に向け速さ1で歩く。
F[i]に到達するとその人は数直線から消える。

各人は歩いている途中何人の人と会うか答えよ。

解法

O(N^2)で間に合うので、愚直に２人の対が互いに会うか合わないか判定すればよい。
問題設定は１次元の数直線だが、もう１次元時間の軸を取り２次元座標を考える。
各人は(T[i],S[i])と(T[i]+|F[i]-S[i]|,F[i])を結んだ線分を移動することになる。

判定する2人の番号をp,qとする。

• 2人が互いに逆向きに歩く場合
  • ２つの線分が交差するか判定すればよい
• 2人が互いに同じ向きに歩く場合
  • ２人の速度は一緒なので、２人が出会うにはある位置を同じ時間に通過している場合があればよい。
  • よって、S[p],F[p],S[q],F[q]の４つの位置について、各人がそこを通るか、また通る時刻が一致するか判定すればよい。

int N;
ll T[1010],S[1010],F[1010];
ll met[2020];

// p1-p2とp3-p4の交差判定
int cross(int x1,int y1,int x2,int y2,int x3,int y3,int x4,int y4) {
	ll XX[3],YY[3];
	XX[0]=x2-x1; YY[0]=y2-y1;
	XX[1]=x3-x1; YY[1]=y3-y1;
	XX[2]=x4-x1; YY[2]=y4-y1;
	ll c1=XX[0]*YY[1]-XX[1]*YY[0];
	ll c2=XX[0]*YY[2]-XX[2]*YY[0];
	if((c1<0&&c2<0)||(c1>0&&c2>0)) return 0;
	XX[0]=x4-x3; YY[0]=y4-y3;
	XX[1]=x1-x3; YY[1]=y1-y3;
	XX[2]=x2-x3; YY[2]=y2-y3;
	c1=XX[0]*YY[1]-XX[1]*YY[0];
	c2=XX[0]*YY[2]-XX[2]*YY[0];
	if((c1<0&&c2<0)||(c1>0&&c2>0)) return 0;
	return 1;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>T[i]>>S[i]>>F[i];
	
	FOR(y,N) FOR(x,y) {
		if((F[y]-S[y])*(F[x]-S[x])>0) {
			int m=0,rev=0;
			if(S[y]>F[y]) rev=1,S[y]*=-1,F[y]*=-1,S[x]*=-1,F[x]*=-1;
			FOR(i,2) {
				if(S[y]<=S[x] && S[x]<=F[y] && T[y]+S[x]-S[y]==T[x]) m=1;
				if(S[y]<=F[x] && F[x]<=F[y] && T[y]+F[x]-S[y]==T[x]+F[x]-S[x]) m=1;
				swap(x,y);
			}
			
			if(rev) S[y]*=-1,F[y]*=-1,S[x]*=-1,F[x]*=-1;
			met[x]+=m;
			met[y]+=m;
		}
		else if(cross(T[y],S[y],T[y]+abs(F[y]-S[y]),F[y],T[x],S[x],T[x]+abs(F[x]-S[x]),F[x])) {
			met[x]++, met[y]++;
		}
	}
	FOR(x,N) _P("%d ",met[x]);
	_P("\n");
	
}

まとめ

同じ向きに歩く場合の処理がちょっと面倒だけど、割と綺麗に書けた？