結果

問題 No.62 リベリオン(Extra)
コンテスト
ユーザー なお
提出日時 2014-11-11 03:45:12
言語 Perl
(5.40.0)
結果
TLE  
実行時間 -
コード長 2,813 bytes
コンパイル時間 531 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 25,600 KB
最終ジャッジ日時 2024-12-31 09:32:27
合計ジャッジ時間 19,278 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other TLE * 3
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.pl syntax OK

ソースコード

diff # 

#!/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'α


こんなのわからんぽよお(´･_･`)
0