結果

問題 No.62 リベリオン(Extra)
コンテスト
ユーザー char134217728
提出日時 2018-01-07 21:41:39
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 62 ms / 5,000 ms
コード長 3,599 bytes
コンパイル時間 2,162 ms
コンパイル使用メモリ 198,432 KB
最終ジャッジ日時 2025-01-05 07:11:27
ジャッジサーバーID
（参考情報） 		judge2 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 3
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:117:1: warning: ISO C++ forbids declaration of ‘main’ with no type [-Wreturn-type]
  117 | main(){
      | ^~~~

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define FORR(i,a,b) for (int i=(a);i>=(b);i--)
#define pb push_back
#define pcnt __builtin_popcount
#define show(x) cout<<#x<<" = "<<x<<endl;
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define fi first
#define se second
#define rng(a) (a.begin()),(a.end())
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define sz(x) (int)(x).size()
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef set<int> si;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pll> vpll;
typedef set<ll> sl;
typedef __int128_t lll;
typedef pair<lll,lll> plll;
typedef vector<lll> vlll;
template<typename T>string join(vector<T>&v)
{stringstream s;FOR(i,0,sz(v))s<<' '<<v[i];return s.str().substr(1);}
int modpow(ll a,ll n,int m){if(a==0)return a;ll p=1;for(;n>0;n/=2,a=a*a%m)if(n&1)p=p*a%m;return(int)p;}
void dout(double d){printf("%.12f\n",d);}

const int iinf = 1e9;
const ll linf = 1e18;
const int mod = 1e9+7;
const double pi = acos(-1);
const double eps = 1e-10;


struct Ieq{
  lll gcd(lll a,lll b){if(a>b)swap(a,b);for(;a>0;b%=a,swap(a,b));return b;}
  lll abs(lll a){return (a<0 ? -a : a);}
  plll _solve(lll x,lll y,lll z){
    if(x==1)return plll(z,0);
    lll m = y/x, _y = y%x, f, s, d;
    plll t = _solve(_y,x,z);
    f = t.second - m*t.first;
    s = t.first;
    if(f<0){
      d = abs(f/y);
      f += d*y;
      s -= d*x;
    }
    if(s<0){
      d = abs(s/x);
      s += d*x;
      f-=d*y;
    }
    return plll(f,s);
  }
  plll solve(lll x, lll y, lll z){
    if(z==0)return plll(0,0);
    if(z<0){
      x*=-1;
      y*=-1;
      z*=-1;
    }
    ll _x=abs(x), _y=abs(y), g=gcd(_x,_y);
    if(g<1||z%g>0) return plll(0, 0);
    _x /= g;
    _y /= g;
    z  /= g;
    if(_x > _y) swap(_x, _y);
    plll t = _solve(_x,_y,z);
    if(abs(x)>abs(y)) swap(t.first, t.second);
    if(x < 0)t.first *= -1;
    if(y < 0)t.second *= -1;
    return t;
  }
};
Ieq ieq;
int q;

bool hit(lll w, lll h, lll d, lll x, lll y, lll vx, lll vy){
  lll z = y*vx - x*vy;
  if(z == 0){
    return (x <= vx * d &&y <= vy * d);
  }else{
    plll t = ieq.solve(w*vy, -h*vx, z);
    if(t.fi == 0 && t.se == 0) return false;
    if(t.fi * w * vy - t.se * h * vx != z) cout << "FAIL\n";
    lll g = ieq.gcd(w*vy, h*vx), _x = (h*vx)/g, _y = (w*vy)/g;
    if(t.fi < 0){
      lll dd = -t.fi/_x + 1;
      t.fi += dd * _x;
      t.se += dd * _y;
    }
    if(t.se < 0){
      lll dd = -t.se/_y + 1;
      t.fi += dd * _x;
      t.se += dd * _y;
    }
    {
      lll dd = t.fi/_x, dd2 = t.se/_y;
      if(dd2 < dd) dd = dd2;
      t.fi -= dd * _x;
      t.se -= dd * _y;
    }
    return (t.fi * w + x <= vx * d && t.se * y + y <= vy * d);
  }
}


main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> q;
  FOR(j, 0, q){
    ll w, h, d, mx, my, hx, hy, vx, vy, _mx, _my;
    cin >> w >> h >> d >> mx >> my >> hx >> hy >> vx >> vy;
    if(vx < 0){
      mx = w - mx;
      hx = w - hx;
      vx *= -1;
    }
    if(vy < 0){
      my = h - my;
      hy = h - hy;
      vy *= -1;
    }
    w *= 2;
    h *= 2;
    bool hi = false;
    FOR(i, 0, 4){
      _mx = ((i&1) ? (w - mx) : mx) - hx;
      _my = ((i&2) ? (h - my) : my) - hy;
      if(_mx < 0) _mx += w;
      if(_my < 0) _my += h;
      if(hit(w, h, d, _mx, _my, vx, vy)){
        cout << "Hit\n";
        hi = true;
        break;
      }
    }
    if(!hi) cout << "Miss\n";
  }
  return 0;
}
0