Problem 1039 : Frisbee Dogs

問題概要

日本語なので本文参照
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1039

解法

シミュレート。
犬がフリスビーをいつ、どこで取るかはフリスビーの位置をfp,速度をfv,犬の速度をV,位置をdとしたとき、(それぞれの量はベクトル)
fp+fv*t=d+t*Vの方程式を解けば求まる。

これは|V|がわかっているので、dを移項して両辺二乗することによりtの二次方程式になるので解ける。

ソースコード

int n,m;
P d[10],dir[10]; double v[10];
P fp[1000],fv[1000];

double get(P &fp,P &fv,P &d,double v,int id){
	P dd=fp-d;
	double a=norm(fv)-v*v,b=dd.real()*fv.real()+dd.imag()*fv.imag(),c=norm(dd);
	//解くべき方程式は at^2 + bx + c = 0
	if(abs(a)<EPS){
		if(abs(b)<EPS)return INF;
		double t=-c/2/b; if(t<0)return INF;
		dir[id]=(dd+fv*t)/t; return t;
	}
	double D=b*b-a*c; if(D<0)return INF;
	double t1=(-b+sqrt(D))/a,t2=(-b-sqrt(D))/a;
	if(t1<0)t1=INF; if(t2<0)t2=INF;
	double t=min(t1,t2); if(t==INF)return INF;
	dir[id]=(dd+fv*t)/t;
	return t;
}

int main()
{
	while(scanf("%d%d",&n,&m),n){
		rep(i,n)scanf("%lf%lf%lf",&d[i].real(),&d[i].imag(),v+i);
		rep(i,m)scanf("%lf%lf%lf%lf",&fp[i].real(),&fp[i].imag(),
			&fv[i].real(),&fv[i].imag());
		int ans[10]={};
		rep(i,m){
			double t[10],mnt=INF;
			rep(j,n)t[j]=get(fp[i],fv[i],d[j],v[j],j);
			rep(j,n)mnt=min(mnt,t[j]);
			rep(j,n){
				if(t[j]!=INF)d[j]+=dir[j]*mnt;
				if(t[j]==mnt)ans[j]++;
			}
		}
		rep(i,n)printf("%d%c",ans[i],i==n-1?'\n':' ');
	}
	return 0;
}