{-# LANGUAGE LambdaCase #-} {-# LANGUAGE ParallelListComp #-} module Main where import Control.Monad pairs :: [a] -> [(a,a)] pairs (x:y:xys) = (x,y) : pairs xys pairs _ = [] type Poly a = [a] type Bezier a = [(a, a)] infixl 6 +$ infixl 7 *$ neg :: Num a => Poly a -> Poly a neg = map (negate) (+$) :: Num a => Poly a -> Poly a -> Poly a (+$) [] ys = ys (+$) xs [] = xs (+$) (x:xs) (y:ys) = x + y : (xs +$ ys) (*$) :: Num a => Poly a -> Poly a -> Poly a (*$) xs [] = [] (*$) xs (y:ys) = (0:xs) *$ ys +$ map (y*) xs deriv :: Num a => Poly a -> Poly a deriv xs = [ fromIntegral n * c | n <- [1..] :: [Integer] | c <- tail xs ] integral :: Fractional a => Poly a -> Poly a integral xs = 0 : [ c / fromIntegral (n + 1) | n <- [0..] :: [Integer] | c <- xs] eval :: Num a => Poly a -> a -> a eval p x = sum [ c * xn | xn <- iterate (*x) 1 | c <- p] bezierToPoly :: Num a => Bezier a -> (Poly a, Poly a) bezierToPoly ps = (go (map fst ps), go (map snd ps)) where go [] = [] go [x] = [x] go xs = [1,-1] *$ go (init xs) +$ [0,1] *$ go (tail xs) area :: Fractional a => [Bezier a] -> a area bs = abs (sum (map go bs)) where go b = eval f 1 - eval f 0 where (x, y) = bezierToPoly b f = integral (neg y *$ deriv x) readInput :: IO [Bezier Double] readInput = do n <- readLn inputs <- replicateM n go pure (tie inputs) where go :: IO [(Double, Double)] go = fmap words getLine >>= case (x0' : y0' : k' : xys') -> do let xy0 = (read x0', read y0') k = read k' xys = map read xys' if length xys /= k * 2 then undefined else pure (xy0 : pairs xys) _ -> undefined tie :: [[(Double, Double)]] -> [Bezier Double] tie is = [ i ++ [t] | i <- is | t <- (tail hs ++ [head hs]) ] where hs = map head is main :: IO () main = do bs <- readInput putStr "순애 드리프트의 면적 : " print (area bs)


예시

$ ./Main 3 0 0 2 -3 2 -2 6 -1 6 2 0 7 -3 3 1 4 3 4 0 1 2 -1 4 순애 드리프트의 면적 : 10.021428571428544


재밌게 풀었음


다항식 곱셈 convolution 같은거 하기 귀찮아서 걍 재귀로 대충 함