結果

問題 No.61 リベリオン
ユーザー krotonkroton
提出日時 2014-11-07 05:05:58
言語 Haskell
(9.8.2)
結果
AC  
実行時間 161 ms / 5,000 ms
コード長 1,993 bytes
コンパイル時間 7,823 ms
コンパイル使用メモリ 174,064 KB
実行使用メモリ 23,552 KB
最終ジャッジ日時 2024-10-13 16:13:09
合計ジャッジ時間 8,477 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 1 ms
5,248 KB
testcase_03 AC 161 ms
23,424 KB
testcase_04 AC 159 ms
23,552 KB
testcase_05 AC 1 ms
5,248 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.8.2/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
0