Haskell卒業!

■ [メモ]TopCoder Open 2010 Round1 03:34

Haskell関係ないけど...

また観戦してしまった...

ACRush氏の1000提出が速かった...

グレイの２位の人には何投げても落ちそうだったが...

GCJより、こっちの方が過酷だな...

過酷と言うか、最後まで生き残るには運の要素が強すぎる気がする...

それでも強者は生き残るが...

上位陣でも久々に参戦みたいな人はほとんどもたついていた...

強い人にチャレンジした時と弱い人にそうした時で成功したポイントが同じってのはなんだかなぁ。現実社会に即していると言えばそうなるが、普通、レーティング差に比例したポイントが貰えるべきかと思うのだが...

強い人同士でポイント奪える(エナジードレインできる、偏差値を奪える)ようにすれば、ゲーム的には面白くなりそうだが、レーティングではなくなってしまうな...

■ [メモ]Haskellプログラマの進化 07:46

Haskellプログラマの進化というページが面白かったのでメモ...

階乗を計算する関数(factorial)を書いてみて、その定義内容によって習熟度を判断するみたいなやつ...

回答例は → The Evolution of a Haskell Programmer

私が定義するとしたら、めんどくさいから

factorial n = product [2 .. n]

とすると思う...

Sophomore Haskell programmer, at MIT(Lisp(Schime)っぽい)を見て、なるほど...

Post-doc Haskell programmerみたいに自分で代数的データ型定義して、型クラス使って色々何かやるのがHaskellの本来的な使い方なんだろうなぁ...

繰り返しや順番を遵守する必要がある処理で、C/C++と張り合おうとするのは間違ってる...

■ [CodeForces]Beta Round 1((C)Ancient Berland Circus)2 13:50

ACした...

誤差1e-9だとTLEだった。よく考えたら、そんな角度のsinとか取っても、すごい小さい値にしかならないと思い、1e-4に変更したら通った...

誤差の計算、やっぱよくわからない...

Text.Printfは使えた。使えなかったら発狂してたな...

import Control.Applicative
import Control.Monad
import Data.List
import Data.Ord
import Text.Printf

epsilon :: Double
-- epsilon = 1e-9
epsilon = 1e-4

cross :: [[Double]] -> Double
cross [[y1, x1], [y2, x2], [y3, x3]] = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1)

distance :: [Double] -> [Double] -> Double
distance [y1, x1] [y2, x2] = sqrt $ (x2 - x1) ^ 2 + (y2 - y1) ^ 2

cap :: Double -> Double
cap = min 1 . max (negate 1)

unitVector :: [Double] -> [Double] -> [Double]
unitVector p1@[y1, x1] p2@[y2, x2] = cap . (/ d) <$> [x2 - x1, y2 - y1]
 where
  d = distance p1 p2

radian p@[y, x] = if y >= 0 then theta else 2 * pi - theta
 where
  theta = acos x
  
centerOfCircle :: [[Double]] -> [Double]
centerOfCircle ps@[[y1, x1], [y2, x2], [y3, x3]]
  | abs (cross ps) < epsilon = error $ "All the points are on a line."
  | otherwise                = [b / a, d / c]
 where
  a = 2 * (y1 * (x3 - x2) + y2 * (x1 - x3) + y3 * (x2 - x1))
  b = (y1 ^ 2 + x1 ^ 2) * (x3 - x2)
    + (y2 ^ 2 + x2 ^ 2) * (x1 - x3)
    + (y3 ^ 2 + x3 ^ 2) * (x2 - x1)
  c = 2 * (x1 * (y3 - y2) + x2 * (y1 - y3) + x3 * (y2 - y1))
  d = (y1 ^ 2 + x1 ^ 2) * (y3 - y2)
    + (y2 ^ 2 + x2 ^ 2) * (y1 - y3)
    + (y3 ^ 2 + x3 ^ 2) * (y2 - y1)

solve :: (Double, Int) -> [Double] -> Double
solve = fmap (((2 * pi) /) . fst) . foldl' search
 where
  search (theta, n) x = (theta / fromIntegral (until check succ n), 1)
   where
    check i
      | x `fmod` t < epsilon = True
      | otherwise            = False
     where
      t = theta / fromIntegral i
      v `fmod` d
        | r < epsilon || abs (1 - r) < epsilon = 0
        | otherwise                            = r
       where
        (_, r) = properFraction $ (v / d)

getDouble :: IO [Double]
getDouble = fmap read . words <$> getLine

main = do
  -- let ps = [[0, 0], [1, 1], [0, 1]]
  -- let ps = [[0, 1], [sqrt 3 / 2, 1 / 2], [0, -1]]
  -- let ps = [[0, 1], [sqrt 2 / 2, sqrt 2 / 2], [0, -1]]
  -- let ps = [[0, 1], [1 / 2, sqrt 3 / 2], [0, -1]]
  ps <- replicateM 3 getDouble
  let c  = centerOfCircle ps
  let [theta1, theta2, theta3] = sort $ radian <$> (unitVector c <$> ps)
  let xs = [theta2 - theta1, theta3 - theta2, 2 * pi - (theta3 - theta1)]
  let n = solve (2 * pi, 1) xs
  let r = distance c (head ps)
  printf "%.7f" $ (r ^ 2 * sin (2 * pi / n) / 2) * n