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; }