メモリを節約しない力業

格子点の列挙です。候補となる格子点の一覧を作成してから、各格子点の距離を求めて距離の小さい順にソートしています。

import Data.List
import Text.Printf

-- x = sqrt(1000)/2
-- pointMax = sqrt(x^2 + x^2)
--          = sqrt(500)
--          ≒ 22.36
pointMax = 22

-- 候補となる点の列挙
targetPoints :: [(Int, Int)]
targetPoints = [(x, y) | x <- [-pointMax..pointMax], y <- [-pointMax..pointMax]]
-- 各点に対して原点からの距離と角度の情報を追加
addDistanceAtan :: [(Int, Int)] -> [(Int, Int, Int, Double)]
addDistanceAtan xs = map (\(x,y) -> (x, y, x^2+y^2, (convertAngle x y))) xs

-- 角度の取得(0〜2π)
convertAngle :: Int -> Int -> Double
convertAngle x y = let a = atan2 (fromIntegral y) (fromIntegral x)
                   in if a >= 0 then a else 2 * pi + a

-- 距離を比較する、距離が同じ場合は角度を比較する
compPointDistance :: (Int, Int, Int, Double) -> (Int, Int, Int, Double) -> Ordering
compPointDistance (_, _, d1, a1) (_, _, d2, a2) =
    let ret = d1 `compare` d2
    in if ret /= EQ then ret else a1 `compare` a2

-- 表示用の文字列に変換する
pointString :: (Int, Int, Int, Double) -> String
pointString (x, y, _, _) = printf "%d, %d" x y

main = do putStrLn $ unlines $ map pointString $ take 1000 $
           sortBy compPointDistance $ addDistanceAtan $ targetPoints