結果

問題 No.61 リベリオン
コンテスト
ユーザー tnakao0123
提出日時 2025-02-03 18:55:58
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 9 ms / 5,000 ms
コード長 2,315 bytes
コンパイル時間 1,730 ms
コンパイル使用メモリ 44,028 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2025-02-03 18:56:01
合計ジャッジ時間 2,168 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 4
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:45:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   45 |   scanf("%d", &qn);
      |   ~~~~~^~~~~~~~~~~
main.cpp:48:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   48 |     scanf("%d%d%d%d%d%d%d%d%d", &w, &h, &d, &mx, &my, &hx, &hy, &vx, &vy);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 61.cc: No.61 繝ｪ繝吶Μ繧ｪ繝ｳ - yukicoder
 */

#include<cstdio>
#include<algorithm>
#include<numeric>
 
using namespace std;

/* constant */

/* typedef */

/* global variables */

/* subroutines */

// exgcd: For given x>0 and y>0, solve a, b, c such that ax+by=c (=gcd(x,y))
template <typename T>
void exgcd(T x, T y, T &a, T &b, T &c) {
  T r0 = x, r1 = y;
  T a0 = 1, a1 = 0;
  T b0 = 0, b1 = 1;

  while (r1 > 0) {
    T q1 = r0 / r1;
    T r2 = r0 % r1;
    T a2 = a0 - q1 * a1;
    T b2 = b0 - q1 * b1;
    r0 = r1, r1 = r2;
    a0 = a1, a1 = a2;
    b0 = b1, b1 = b2;
  }
  c = r0;
  a = a0;
  b = b0;
}

/* main */

int main() {
  int qn;
  scanf("%d", &qn);
  while (qn--) {
    int w, h, d, mx, my, hx, hy, vx, vy;
    scanf("%d%d%d%d%d%d%d%d%d", &w, &h, &d, &mx, &my, &hx, &hy, &vx, &vy);

    int w2 = w * 2, h2 = h * 2;
    if (vx < 0) mx = w - mx, hx = w - hx, vx = -vx;
    if (vy < 0) my = h - my, hy = h - hy, vy = -vy;

    if (vx == 0) {
      if (mx == hx) {
	int dy = (my >= hy) ? (my - hy) : (h2 - my - hy);
	if (vy * d >= dy) { puts("Hit"); continue; }
      }
      puts("Miss"); continue;
    }
    
    if (vy == 0) {
      if (my == hy) {
	int dx = (mx >= hx) ? (mx - hx) : (w2 - mx - hx);
	if (vx * d >= dx) { puts("Hit"); continue; }
      }
      puts("Miss"); continue;
    }
    
    // hx+t*vx=a*w2+mx,hy+t*vy=b*h2+my
    // -> t=(a*w2+mx-hx)/vx=(b*h2+my-hy)/vy
    // -> vy(a*w2+mx-hx)=vx(b*h2+my-hy)
    // -> a(vy*w2)-b(vx*h2)=vx(my-hy)-vy(mx-hx)

    int x = vy * w2, y = vx * h2;
    int a, b, g;
    exgcd(x, y, a, b, g);

    bool hit = false;
    for (int bits = 0; bits < 4; bits++) {
      int mx0 = (bits & 1) ? w2 - mx : mx;
      int my0 = (bits & 2) ? h2 - my : my;
      
      int z = vx * (my0 - hy) - vy * (mx0 - hx);
      if (z % g != 0) continue;

      a *= z / g, b *= z / g;
      int l = x / gcd(x, y) * y;
      int da = l / x, db = l / y;

      if (a < 0) {
	int q = (-a + da - 1) / da;
	a += q * da, b -= q * db;
      }
      if (a >= da) {
	int q = a / da;
	a -= q * da, b += q * db;
      }
      //printf(" a=%d, b=%d, da=%d, db=%d\n", a, b, da, db);

      int dx = a * w2 + mx0 - hx;
      if (vx * d >= dx) { hit = true; break; }
    }

    if (hit) puts("Hit");
    else puts("Miss");
  }
  return 0;
}
0