かっさのなにか

僕も生涯現役競プロ人間になりたい

AOJ 2609 Wave Atacck JAG summer 2013 (NU contest 14 B)

幾何もどき

問題概要

Wave Attack | Aizu Online Judge

W×Hの箱の中で、(X,Y)から衝撃波が来る。この衝撃波は速度vで衝撃波を全方向に出し、t秒までこの衝撃波は有効である。衝撃波は箱の中で壁にぶつかると反射する。
(P,Q)にいる伯爵に何回当たるか。
v×t≤10^6
2≤W,H≤10^8
0＜X,P＜W
0＜Y,Q＜H
(X,Y)≠(P,Q)

解説

衝撃波が折り返して反射してくるのを考えるのがとても大変なので、衝撃が壁に反射した際の円は折り返さないとする。
f:id:Yang33-kassa:20170708010343p:plainf:id:Yang33-kassa:20170708010325p:plain
その代わり箱をたくさん作り、
辺を折り返した際に対称になるような位置に伯爵がいるとする。
f:id:Yang33-kassa:20170708010328p:plainf:id:Yang33-kassa:20170708010330p:plain
このとき、問題は(X,Y)を中心とした円の中にどれだけ点が存在するか
という問題に書き換えられる。円の半径はTVである。伯爵の位置についてみると、
最初の箱を基準にした際にX座標は ...,-4W-P,-4W+P,-2W-P, -2W+P -P,P,2W-P,2W+P,4W-P,4W+P,...
Y座標も同様に周期2の座標しかないことが分かる。
Xの幅についてVT≦10^6,箱のサイズは2≦Wであるから各x座標についてその縦列にある点の数を数える。

その列の円の重なる部分のY座標は、列のX座標と衝撃波の発射地点から分かる。\sqrt{r^2-x^2}
円が非常に小さい場合を除いて、この円の下には必ず点があるので
これは高さをHで割れば点の個数が分かる。

必ず点が含まれている領域の一つ上の領域に含まれる点についてこの点が含まれるかどうかは分からないのでこれについては具体的な座標を求めて円に含まれるかを検査する。
f:id:Yang33-kassa:20170708010334p:plainf:id:Yang33-kassa:20170708010338p:plain
これを上下左右について場合分けをして点の数を足していけばよい。
この話は円の下からX,Y軸までは必ず覆われている前提であったので、
例外処理は右上の領域について、最も円の中心に近い点が円に含まれない場合はカウントをしないとすればよい。
↓ダメなケース
f:id:Yang33-kassa:20170708010340p:plain

コード

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define FOR(i, s, e) for (ll(i) = (s); (i) < (e); (i)++)
#define debug(x) cout << #x << ": " << x << endl

/* -----  2017/07/07  Problem: AOJ 2609 jag summer 2013 Wave Atacck (NU contest 14 B)
/ Link: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2609  ----- */

ll W, H, V, T, X, Y, P, Q;
ll ans = 0LL;

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);

	cin >> W >> H >> V >> T >> X >> Y >> P >> Q;
	ll width = V*T + X;

	width = (width + W - 1) / W;

	//sの右側
	ll r = V*T;
	FOR(i, 0, width) {
		ll x;
		if (i % 2 == 0) { x = (i + 1) / 2 * 2 * W + P; }
		else { x = (i + 1) / 2 * 2 * W - P; }
		//上
		ll dx = x - X;
		double  kyoukaiY = sqrt(r*r - dx*dx) + Y;
		if (pow(X - x, 2) + pow(Y - Q, 2) > r*r)continue;
		//一つ目の点が内側にないときはそもそもどの点も内包されない


		ll hnum = kyoukaiY / H;
		ans += hnum;
		ll y, dy;
		if (hnum % 2 == 0) { //奇数番目が入るかわからない
			y = hnum*H + Q;
			dy = y - Y;
		}
		else { // 偶数番目が入るかわからない
			y = ((hnum + 1) / 2) * 2 * H - Q;
			dy = y - Y;
		}

		if ((r*r >= dx*dx + dy*dy)) {
			ans++;
		}

		//下
		dx = x - X;
		kyoukaiY = sqrt(r*r - dx*dx) - Y;
		if (kyoukaiY < 0)continue;
		hnum = kyoukaiY / H;
		ans += hnum;

		if (hnum % 2 == 0) { //奇数番目が入るかわからない
			y = hnum*H + Q;
			dy = y + Y;
		}
		else { // 偶数番目が入るかわからない
			y = ((hnum + 1) / 2) * 2 * H - Q;
			dy = y + Y;
		}

		if ((r*r >= dx*dx + dy*dy)) {
			ans++;
		}
	}


	//左
	width = abs(-r + X);
	width = (width + W - 1) / W;
	FOR(i, 0, width) {
		ll x;
		if (i % 2 == 0) { x = -((i + 1) / 2 * 2 * W + P); }// 左と同じ
		else { x = -((i + 1) / 2 * 2 * W - P); }

		ll dx = abs(x) + X;
		ll y, dy;

		//上
		double kyoukaiY = sqrt(r*r - dx*dx) + Y;
		ll hnum = kyoukaiY / H;
		ans += hnum;
		if (hnum % 2 == 0) {// 次奇数番目が入るかのチェック
			y = hnum*H + Q;
			dy = y - Y;
		}
		else {// 次奇偶数番目が入るかのチェック
			y = ((hnum + 1) / 2) * 2 * H - Q;
			dy = y - Y;
		}

		if ((r*r >= dx*dx + dy*dy)) {
			ans++;
		}

		//下
		dx = abs(x) + X;

		kyoukaiY = sqrt(r*r - dx*dx) - Y;
		if (kyoukaiY < 0)continue;
		hnum = kyoukaiY / H;
		ans += hnum;

		if (hnum % 2 == 0) { //奇数番目が入るかわからない
			y = hnum*H + Q;
			dy = y + Y;

		}
		else { // 偶数番目が入るかわからない
			y = ((hnum + 1) / 2) * 2 * H - Q;
			dy = y + Y;
		}

		if ((r*r >= dx*dx + dy*dy)) {
			ans++;
		}

	}

	cout << ans << endl;

	return 0;
}