読者です 読者をやめる 読者になる 読者になる

ヘクトのメモ

なんとなくいろいろ書いていくと思います.

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