幅 $W$，高さ $H$ の箱がある．
$(H_x,H_y)$ から速度 $(V_x,V_y)$ で玉を発射した．
摩擦などはないとし玉は速度を落とさず，壁にあたったら完全弾性衝突する．
時間 $T$ 以内に玉が $1$ 度でも $(M_x,M_y)$ に辿り着くことがあるかどうかを判定する問題．
問題原文の図も参照．
壁は鏡のように折り返して考えて無限に広い $2$ 次元平面にして，ターゲットは $4$ 系列の点が周期的（$X$ 方向に周期 $2W$，$Y$ 方向に周期 $2H$）に並んでいると思う．
それぞれの系列のターゲットに対して，最初にぶつかる場所を計算し，そこまで時間 $T$ 以内で行けるかどうかを判定すれば良い．
それは，移動する直線上に，ターゲットの点が乗っているという式を立て，その解の $1$ つを拡張ユークリッドの互除法で解き，周期性に着目して最も近い点を探せば良い．
普通に計算すると途中で $10^{18}$ の $3$ 乗程度の値が出てくるので多倍長整数を用いた．
シミュレーションでも解ける制約の小さいバージョンはこちら（yukicoder No.61 リベリオン）．
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
#define ll long long
#define BIG_INT_SIZE 7
#define BIG_INT_BASE 100000000LL
#define BIG_INT_DIGITS 8
#define BIG_INT_CHAR_SIZE 1000 /* BIG_INT_SIZE*BIG_INT_DIGITS+2以上 */
typedef struct big_integer{ll a[BIG_INT_SIZE];}bigInt;
int bigIntSign(bigInt a);
int bigIntToChar(bigInt a,char ret[]);
void printBigInt(bigInt a);
void putBigInt(bigInt a);
bigInt bigIntZero(){
bigInt a; int i;
rep(i,BIG_INT_SIZE) a.a[i]=0;
return a;
}
bigInt bigIntOne(){
bigInt a; int i;
REP(i,1,BIG_INT_SIZE) a.a[i]=0; a.a[0]=1;
return a;
}
bigInt bigIntOrder(bigInt a){
int i; ll k;
REP(i,1,BIG_INT_SIZE) if(a.a[i-1]<0 || a.a[i-1]>=BIG_INT_BASE){
k=a.a[i-1]/BIG_INT_BASE; a.a[i-1]-=k*BIG_INT_BASE;
if(a.a[i-1]<0) k--, a.a[i-1]+=BIG_INT_BASE; a.a[i]+=k;
}
if(a.a[BIG_INT_SIZE-1]<0){
rep(i,BIG_INT_SIZE) a.a[i]=-a.a[i]; a=bigIntOrder(a);
rep(i,BIG_INT_SIZE) a.a[i]=-a.a[i];
}
return a;
}
bigInt llToBigInt(ll a){
bigInt c; int i;
REP(i,1,BIG_INT_SIZE) c.a[i]=0; c.a[0]=a;
return bigIntOrder(c);
}
int bigIntGreaterThan(bigInt a,bigInt b){
int i;
for(i=BIG_INT_SIZE-1;i>=0;i--){
if(a.a[i]>b.a[i]) return 1;
if(a.a[i]<b.a[i]) return 0;
}
return 0;
}
int bigIntIsZero(bigInt a){
int i; rep(i,BIG_INT_SIZE) if(a.a[i]) return 0; return 1;
}
bigInt bigIntPlus(bigInt a,bigInt b){
int i; bigInt c;
rep(i,BIG_INT_SIZE) c.a[i]=a.a[i]+b.a[i];
return bigIntOrder(c);
}
bigInt bigIntMinus(bigInt a,bigInt b){
int i; bigInt c;
rep(i,BIG_INT_SIZE) c.a[i]=a.a[i]-b.a[i];
return bigIntOrder(c);
}
bigInt bigIntMultipleLL(bigInt a,ll b){
int i; rep(i,BIG_INT_SIZE) a.a[i]*=b;
return bigIntOrder(a);
}
bigInt bigIntPlusSimple(bigInt a,bigInt b){
int i; bigInt c;
rep(i,BIG_INT_SIZE) c.a[i]=a.a[i]+b.a[i];
return c;
}
bigInt bigIntMinusSimple(bigInt a,bigInt b){
int i; bigInt c;
rep(i,BIG_INT_SIZE) c.a[i]=a.a[i]-b.a[i];
return c;
}
bigInt bigIntMultipleLLSimple(bigInt a,ll b){
int i; rep(i,BIG_INT_SIZE) a.a[i]*=b;
return a;
}
bigInt bigIntMultiple(bigInt a,bigInt b){
int i,j,ii,jj; bigInt c;
for(ii=BIG_INT_SIZE-1;ii;ii--) if(a.a[ii]) break; ii++;
if(ii==1) return bigIntMultipleLL(b,a.a[0]);
for(jj=BIG_INT_SIZE-1;jj;jj--) if(b.a[jj]) break; jj++;
if(jj==1) return bigIntMultipleLL(a,b.a[0]);
rep(i,BIG_INT_SIZE) c.a[i]=0;
rep(i,ii)if(a.a[i])for(j=0;j<jj&&i+j+1<BIG_INT_SIZE;j++) c.a[i+j]+=a.a[i]*b.a[j];
return bigIntOrder(c);
}
void bigIntDivisionsLL(bigInt a,ll b,bigInt *c,ll *d){
int i;
rep(i,BIG_INT_SIZE) c->a[i]=a.a[i];
for(i=BIG_INT_SIZE-1;i;i--)
c->a[i-1]+=(c->a[i]%b)*BIG_INT_BASE, c->a[i]/=b;
*d = c->a[0]%b; c->a[0]/=b;
}
/* c=a/b, d=a%b */
void bigIntDivisions(bigInt a,bigInt b,bigInt *c,bigInt *d){
int i,j,s,sa,sb; ll ma,mb,mc; bigInt tmp;
sa=bigIntSign(a); sb=bigIntSign(b);
if(sa==-1) a=bigIntMultipleLL(a,-1);
if(sb==-1) b=bigIntMultipleLL(b,-1);
for(j=BIG_INT_SIZE-1;j;j--) if(b.a[j]) break;
if(!j){
REP(i,1,BIG_INT_SIZE) d->a[i]=0;
bigIntDivisionsLL(a,b.a[0],c,&(d->a[0]));
}else{
for(i=BIG_INT_SIZE-1;i;i--) if(a.a[i]) break;
s=i-j; if(s<0) s=0;
rep(i,BIG_INT_SIZE) c->a[i]=0;
while(s>=0){
ma=0; mb=BIG_INT_BASE-1;
while(ma!=mb){
mc = (ma+mb)/2 + (ma+mb)%2;
c->a[s]=mc; tmp=bigIntMultiple(*c,b);
if(bigIntGreaterThan(tmp,a)) mb=mc-1; else ma=mc;
}
c->a[s]=ma; s--;
}
tmp = bigIntMultiple(b,*c);
*d = bigIntMinus(a,tmp);
}
if(sa==-1 && sb==-1){
*d=bigIntMultipleLL(*d,-1);
} else if(sa==-1 && sb!=-1){
*c=bigIntMultipleLL(*c,-1);
*d=bigIntMultipleLL(*d,-1);
} else if(sa!=-1 && sb==-1){
*c=bigIntMultipleLL(*c,-1);
}
}
bigInt bigIntDivision(bigInt a,bigInt b){
bigInt c,d;
bigIntDivisions(a,b,&c,&d);
return c;
}
int bigIntSign(bigInt a){
int i;
for(i=BIG_INT_SIZE-1;i>=0;i--) if(a.a[i]){
if(a.a[i]<0) return -1; else return 1;
}
return 0;
}
bigInt bigIntAbs(bigInt a){
if(bigIntSign(a)==-1) return bigIntMultipleLL(a,-1LL); return a;
}
void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(int *x, int *y){reader(x);reader(y);}
void reader(int *x, int *y, int *z){reader(x);reader(y);reader(z);}
void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);}
template<class T> T GCD(T a,T b){T r; while(a){r=b; b=a; a=r%a;} return b;}
void extended_euclid(ll x,ll y,ll *c,ll *a,ll *b){
ll a0,a1,a2,b0,b1,b2,r0,r1,r2,q;
r0=x; r1=y; a0=1; a1=0; b0=0; b1=1;
while(r1>0){
q=r0/r1; r2=r0%r1; a2=a0-q*a1; b2=b0-q*b1;
r0=r1; r1=r2; a0=a1; a1=a2; b0=b1; b1=b2;
}
*c=r0; *a=a0; *b=b0;
}
bigInt big;
int solve(ll Vx, ll Vy, ll Sx, ll Sy, ll Dx, ll Dy){
if(Vx < 0) return solve(-Vx, Vy, -Sx, Sy, Dx, Dy);
if(Vy < 0) return solve(Vx, -Vy, Sx, -Sy, Dx, Dy);
int i;
ll VVx, VVy, X, Y, g, A, B, C, D, XX, YY, Bx, By;
bigInt BBx, BBy, gg, gg1, gg2;
g = GCD(Vx, Vy);
VVx = Vx / g;
VVy = Vy / g;
g = Sx / Dx;
Sx -= g * Dx;
g = Sy / Dy;
Sy -= g * Dy;
while(Sx < 0) Sx += Dx; while(Sx >= Dx) Sx -= Dx;
while(Sy < 0) Sy += Dy; while(Sy >= Dy) Sy -= Dy;
A = Dx * VVy;
B = Dy * VVx;
C = VVx * Sy - VVy * Sx;
if(A && B){
g = GCD(A,B);
if(C%g) return 0;
A /= g; B /= g; C /= g;
extended_euclid(A, B, &D, &X, &Y);
BBx = bigIntMultiple(llToBigInt(C), llToBigInt(X));
BBy = bigIntMultiple(llToBigInt(-C), llToBigInt(Y));
gg1 = bigIntDivision(BBx, llToBigInt(B));
gg2 = bigIntDivision(BBy, llToBigInt(A));
if(bigIntGreaterThan(gg1,gg2)) gg = gg2; else gg = gg1;
BBx = bigIntMinus(BBx, bigIntMultiple(gg, llToBigInt(B)));
BBy = bigIntMinus(BBy, bigIntMultiple(gg, llToBigInt(A)));
if(bigIntGreaterThan(BBx, big)) return 0;
if(bigIntGreaterThan(BBy, big)) return 0;
Bx = By = 0;
rep(i,BIG_INT_SIZE) Bx = Bx * BIG_INT_BASE + BBx.a[BIG_INT_SIZE-1-i];
rep(i,BIG_INT_SIZE) By = By * BIG_INT_BASE + BBy.a[BIG_INT_SIZE-1-i];
while(Bx-B >= 0 && By-A >= 0) Bx -= B, By -= A;
while(Bx < 0 || By < 0) Bx += B, By += A;
} else {
Bx = By = 0;
}
if((double)Bx * Dx > 2e18) return 0;
if((double)By * Dy > 2e18) return 0;
XX = Sx + Bx * Dx;
YY = Sy + By * Dy;
if(XX <= Vx && YY <= Vy) return 1;
return 0;
}
int Q;
int W, H, D, HX, HY, MX, MY, VX, VY;
int main(){
int i, j, k;
big = llToBigInt(2000000000000000000LL);
reader(&Q);
while(Q--){
reader(&W,&H,&D);
reader(&MX,&MY);
reader(&HX,&HY);
reader(&VX,&VY);
k = 0;
if(!k) k |= solve((ll)VX*D, (ll)VY*D, MX-HX, MY-HY, 2*W, 2*H);
if(!k) k |= solve((ll)VX*D, (ll)VY*D, (2*W-MX)-HX, MY-HY, 2*W, 2*H);
if(!k) k |= solve((ll)VX*D, (ll)VY*D, MX-HX, (2*H-MY)-HY, 2*W, 2*H);
if(!k) k |= solve((ll)VX*D, (ll)VY*D, (2*W-MX)-HX, (2*H-MY)-HY, 2*W, 2*H);
writer(k?"Hit\n":"Miss\n");
}
return 0;
}
Current time: 2024年04月26日08時57分27秒
Last modified: 2014年11月12日00時00分16秒 (by laycrs)
Tags: Competitive_Programming yukicoder
トップページに戻る
Logged in as: unknown user (not login)