#!/usr/bin/perl use strict; use bigint; sub max{return($_[0]>$_[1]?$_[0]:$_[1])} sub gcd{return($_[1]?gcd($_[1],$_[0]%$_[1]):$_[0])} # am + bn = gcd(a, b) sub extgcd{ my($a,$b)=@_; my($g,$m,$n)=($a,1,0); if($b){ ($g,$n,$m) = extgcd($b, $a % $b); $n -= ($a/$b)*$m; } return ($g,$m,$n); } sub min_k{ my($a,$b)=@_; return (-$b + $a - 1) / $a if($b < 0); return -($b / $a); } sub colcheck{ my($W,$H,$D,$Mx,$My,$Hx,$Hy,$Vx,$Vy) = @_; my $a = 2 * $W * $Vy; my $b = 2 * $H * $Vx; my $c = $Vx * ($My - $Hy) - $Vy * ($Mx - $Hx); my $g = gcd($a, $b); return 0 if($c % $g != 0); $a /= $g; $b /= $g; $c /= $g; my(undef,$alpha,$beta) = extgcd($a, $b); my $min_n = min_k($W * 2, $Mx - $Hx - 1); my $min_m = min_k($H * 2, $My - $Hy - 1); my $k = max( min_k($b, $c * $alpha - $min_n), min_k($a, -$c * $beta - $min_m) ); my $n = $b * $k + $c * $alpha; my $m = $a * $k - $c * $beta; my $x = $W * 2 * $n + $Mx; my $y = $H * 2 * $m + $My; return ($x-$Hx)**2 + ($y-$Hy)**2 <= ($Vx*$D)**2 + ($Vy*$D)**2; } sub linecheck{ my ($S,$D,$M,$H,$V) = @_; if($H < $M){ return ($M-$H <= $V*$D); # 直接 } else { return ( $S*2-$H-$M <= $V*$D ); # 1回壁反射 } } sub check{ my($W,$H,$D,$Mx,$My,$Hx,$Hy,$Vx,$Vy) = @_; if($Vx < 0){ ($Mx,$Hx,$Vx)=($W-$Mx,$W-$Hx,-$Vx); } if($Vy < 0){ ($My,$Hy,$Vy)=($H-$My,$H-$Hy,-$Vy); } if($Vx == 0){ return 0 if($Hx != $Mx); return linecheck($H,$D,$My,$Hy,$Vy); } if($Vy == 0){ return 0 if($Hy != $My); return linecheck($W,$D,$Mx,$Hx,$Vx); } return 1 if colcheck($W,$H,$D,$Mx ,$My ,$Hx,$Hy,$Vx,$Vy); return 1 if colcheck($W,$H,$D,$W*2-$Mx,$My ,$Hx,$Hy,$Vx,$Vy); return 1 if colcheck($W,$H,$D,$Mx ,$H*2-$My,$Hx,$Hy,$Vx,$Vy); return 1 if colcheck($W,$H,$D,$W*2-$Mx,$H*2-$My,$Hx,$Hy,$Vx,$Vy); return 0; } my $Q = <>; for(1..$Q){ if(check(split/\s+/,<>)){ print "Hit\n"; } else { print "Miss\n"; } } __END__ y - Hy = Vy/Vx(x-Hx) x = Xs+2W*n, y = Ys + 2H*m ys + 2H*m - Hy = Vy/(Xs+2W*n - Hx) Vx * (Ys + 2H*m - Hy) = Vy * (Xs+2W*n - Hx) 2W * Vy * n + 2H * Vx * (-m) = Vx * (Ys - Hy) - Vy * (Xs - Hx) a = 2W * Vy, b = 2H * Vx, c = Vx * (Ys - Hy) - Vy * (Xs - Hx) an + b(-m) = c; g = gcd(a,b) a' = a/g, b' = b/g, c' = c/g a'n + b'(-m) = c' a'α + b'β = 1 .. extgcd a'c'α + b'c'β - a'n - b'(-m) = 0 a'(n - c'α) + b'(-m - c'β) = 0 a'(n - c'α) ≡ 0 (mod b') n - c'α ≡ 0 (mod b') ⇔ n - c'α = b'k a'b'k + b'(-m - c'β) = 0 m = a'k - c'β n = b'k + c'α こんなのわからんぽよお(´・_・`)