import qualified Data.Map as Map import qualified Data.List as List data Platform = Platform Int Int Int String deriving (Show,Eq) -- l r y name platformName (Platform _ _ _ n) = n platformHeight (Platform _ _ y _) = y world :: [Platform] world = [ Platform 0 264 0 "a" , Platform 1 48 32 "b" , Platform 32 112 48 "c" , Platform 80 144 16 "d" , Platform 128 192 64 "e" , Platform 80 96 80 "f" , Platform 16 72 96 "g" , Platform 176 240 32 "h" , Platform 208 224 16 "i" , Platform 160 208 45 "j" , Platform 160 224 96 "k" ] queries = [ (56, 64) , (128, 40) , (176, 56) ] answers = [ "c", "d", "j" ] type SlabDS = Map.Map Int Platform type PointLocDS = Map.Map Int SlabDS data EventKind = Insert | Delete deriving (Show,Eq) type Event = (Int,EventKind,Platform) -- | Compute all x-coordinates where the vertical line starts/stops to -- intersect a platform. events :: [Platform] -> [Event] events = List.sortOn (\(a,b,c) -> a) . concatMap (\p@(Platform l r _ _) -> [(l,Insert,p),(r,Delete,p)]) -- | Build the point location data structure by sweeping a vertical -- line from left to right over the platforms. build :: [Platform] -> PointLocDS build = Map.fromAscList . List.scanl' handle (-10,Map.empty) . events where handle :: (Int,SlabDS) -> Event -> (Int,SlabDS) handle (_,m) (x,Insert,p) = (x,Map.insert (platformHeight p) p m) handle (_,m) (x,Delete,p) = (x,Map.delete (platformHeight p) m) -- | finds the ground below (x,y) query :: (Int,Int) -> PointLocDS -> Maybe (Int,Platform) query (x,y) ds = case Map.lookupLE x ds of Nothing -> Nothing Just (_,m) -> Map.lookupLE y m -- | The data structure for the input above myDS :: PointLocDS myDS = build world test = map (\q -> query q myDS) queries