AOJ 2609 Wave Attack
座標の範囲に不注意で2WAくらい.
解法は分かりやすいけど,バグなく実装するのは難しい
問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2609
解法
反射ということで,鏡像を考える.
衝撃波が届くx座標について
y座標の上限と下限を二分探索して回数を数える.
ソースコードは以下の通り
ll w,h,v,t,x,y,p,q; inline ll xget(ll i){ ll res=p; if(i&1){ res+=2*(w-p); res+=w*(i-1); }else{ res+=w*i; } return res; } inline ll yget(ll i){ ll res=q; if(i&1){ res+=2*(h-q); res+=h*(i-1); }else{ res+=h*i; } return res; } int main(void){ cin >> w >> h >> v >> t >> x >> y >> p >> q; ll ans=0; ll d=(v*t)*(v*t); int dmax=(v*t)/w+10; for(int i=-dmax;i<=dmax;++i){ ll xcur=xget(i)-x; ll ycursq=d-xcur*xcur; if(ycursq<0) continue; ll ylimit=sqrt(ycursq)/h; ll l=-1,r=ylimit+10; while(r-l>1){ ll m=(r+l)/2; ll ycur=yget(m)-y; if(ycur*ycur<=ycursq) l=m; else r=m; } ll upper=l; l=-ylimit-10,r=1; while(r-l>1){ ll m=(r+l)/2; ll ycur=yget(m)-y; if(ycur*ycur<=ycursq) r=m; else l=m; } ll lower=r; ll cur=0; if(lower<=0) cur-=lower; if(0<=upper) cur+=upper; if(lower<=upper) cur++; ans+=cur; } cout << ans << endl; return 0; }