結果

問題 No.62 リベリオン(Extra)
ユーザー krotonkroton
提出日時 2014-11-10 02:18:18
言語 Haskell
(9.10.1)
結果
AC  
実行時間 423 ms / 5,000 ms
コード長 1,993 bytes
コンパイル時間 5,589 ms
コンパイル使用メモリ 182,352 KB
実行使用メモリ 54,912 KB
最終ジャッジ日時 2025-02-07 08:40:23
合計ジャッジ時間 3,350 ms
ジャッジサーバーID
(参考情報)
judge3 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 3
権限があれば一括ダウンロードができます
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.10.1/environments/default
[1 of 2] Compiling Main             ( Main.hs, Main.o )
Main.hs:4:1: warning: [GHC-94817] [-Wtabs]
    Tab character found here, and in 61 further locations.
    Suggested fix: Please use spaces instead.
  |
4 |         where
  | ^^^^^^^^

[2 of 2] Linking a.out

ソースコード

diff #
プレゼンテーションモードにする

extgcd :: Integer -> Integer -> (Integer, Integer)
extgcd a 0 = (1, 0)
extgcd a b = (y, x - (a `div` b) * y)
where
(x, y) = extgcd b (a `mod` b)
min_k :: Integer -> Integer -> Integer
min_k a c | c < 0 = (-c + a - 1) `div` a
| otherwise = -(c `div` a)
collision_check :: [Integer] -> Bool
collision_check [w, h, d, hx, hy, vx, vy, xs, ys]
| c `mod` g /= 0 = False
| otherwise = (x - hx) ^ 2 + (y - hy) ^ 2 <= (vx ^ 2 + vy ^ 2) * d ^ 2
where
a = 2 * w * vy
b = 2 * h * vx
c = vx * (ys - hy) - vy * (xs - hx)
g = gcd a b
a' = a `div` g
b' = b `div` g
c' = c `div` g
(alpha, beta) = extgcd a' b'
min_n = min_k (2 * w) (xs - hx - 1)
min_m = min_k (2 * h) (ys - hy - 1)
k = max
(min_k b' (c' * alpha - min_n))
(min_k a' (-c' * beta - min_m))
n = b' * k + c' * alpha
m = a' * k - c' * beta
x = 2 * w * n + xs
y = 2 * h * m + ys
line_check :: [Integer] -> Bool
line_check [w, d, mx, hx, vx] = dist <= vx * d
where
dist = if (mx > hx)
then mx - hx
else (w - hx) * 2 + hx - mx
check :: [Integer] -> Bool
check [w, h, d, mx, my, hx, hy, vx, vy]
| vx < 0 = check [w, h, d, w - mx, my, w - hx, hy, -vx, vy]
| vy < 0 = check [w, h, d, mx, h - my, hx, h - hy, vx, -vy]
| vx == 0 = (mx == hx) && line_check [h, d, my, hy, vy]
| vy == 0 = (my == hy) && line_check [w, d, mx, hx, vx]
| otherwise = any
(\(xs, ys) -> collision_check [w, h, d, hx, hy, vx, vy, xs, ys])
[
(mx, my),
(mx + (w - mx) * 2, my),
(mx, my + (h - my) * 2),
(mx + (w - mx) * 2, my + (h - my) * 2)
]
readInt :: IO Int
readInt = fmap read getLine
readInts :: IO [Integer]
readInts = fmap ((map read) . words) getLine
printer :: Bool -> IO ()
printer True = putStrLn "Hit"
printer _ = putStrLn "Miss"
main = do
q <- readInt
inputs <- sequence (replicate q readInts)
mapM_ (printer . check) inputs
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0