結果

問題 No.61 リベリオン
コンテスト
ユーザー LayCurse
提出日時 2014-11-10 08:46:37
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 8 ms / 5,000 ms
コード長 2,756 bytes
コンパイル時間 1,185 ms
コンパイル使用メモリ 159,120 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-13 16:13:20
合計ジャッジ時間 1,617 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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

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

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

  ll VVx, VVy, X, Y, g, A, B, C, D, XX, YY, Bx, By;

//  printf("V %lld %lld , S %lld %lld, D %lld %lld\n",Vx,Vy,Sx,Sy,Dx,Dy);
  
  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;

  g = GCD(A,B);
  if(C%g) return 0;
  A /= g; B /= g; C /= g;

//  printf("ABC %lld %lld %lld\n",A,B,C);
  
  extended_euclid(A, B, &D, &X, &Y);
  Bx = C*X; By = -C*Y;
//  printf("XY %lld %lld\n",X,Y);
//  printf("XYB %lld %lld\n",Bx,By);

  if(A && B){
    g = min(Bx / B, By / A);
    Bx -= g * B;
    By -= g * A;
    while(Bx-B >= 0 && By-A >= 0) Bx -= B, By -= A;
    while(Bx < 0 || By < 0) Bx += B, By += A;
  } else {
    Bx = By = 0;
  }

//  printf("XYB %lld %lld\n",Bx,By);
  
  XX = Sx + Bx * Dx;
  YY = Sy + By * Dy;

//  printf("XY %lld %lld\n",XX,YY);

  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;

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