Find angle between two images of a constellation

I am given two images of a constellation differing by an angle and I need to find that angle $ \theta$ . This is a problem of this past contest

Here is my idea:

  • If first image is $ [p_0, p_1, … p_n]$ then the other image would be $ [p_{\pi(1)}\cdot R_\theta,p_{\pi(2)}\cdot R_\theta,…]$ where $ R_{\theta}=\begin{pmatrix}\cos \theta&\sin\theta\-\sin\theta&\cos \theta\end{pmatrix}$ and $ \pi:{\mathbb Z_n }\mapsto{\mathbb Z_n}$ is a permutation.

  • We can consider the cyclic path from $ p_0$ to $ p_1$ and so on and back to $ p_0$ . We can find angle of rotation we make at a point $ p_i$ , i.e. if the angle between $ p_i-p_{i-1}$ and $ p_{i+1}-p_i$ . Let us denote this by $ \Delta\theta_i$ in first image and $ \Delta\theta’_i$ in second image.

  • This will remain same for both the images and we can find find the index $ j=\pi(1)$ such that $ \Delta\theta_1=\Delta\theta’_{j}$ .

  • Now the required angle would be the angle between $ p_2-p_1$ and $ p_{j+1}-p_j$ .

Now I wrote this code but I am getting ‘Wrong Answer’, so what am I doing wrong?

import           Control.Monad import           Control.Arrow import           Data.List import           System.IO  type Point = (Double, Double)  main :: IO () main = do     h         <- openFile "d.in" ReadMode     n         <- read <$  > hGetLine h     (ps, ps') <- splitAt n         <$  > replicateM (2 * n) ((\[a, b] -> (a, b)) . map read . words <$  > hGetLine h)     let qs    = getDeltas ps         qs'   = getDeltas ps'         rs    = getDeltas' qs         rs'   = getDeltas' qs'         idx   = getMatchingIndex rs rs'         theta = head qs - (qs' !! idx)         delta = head rs - (rs' !! idx)     when (abs delta > 1e-5) $   error "No soution"     h' <- openFile "d.out" WriteMode     hPrint h' $   if theta < 0 then theta + 2 * pi else theta     hClose h'  getDeltas' :: [Double] -> [Double] getDeltas' xs = map (\theta -> if theta < 0 then theta + 2 * pi else theta)     $   zipWith (-) (tail $   cycle xs) xs  getAngle :: Point -> Point -> Double getAngle (x, y) (x', y') =     let theta = atan2 y' x' - atan2 y x -- [-pi, pi] - [-pi, pi] = [-2pi, 2pi]     in  if theta < 0 then theta + 2 * pi else theta -- [0, 2pi]  getDeltas :: [Point] -> [Double] -- [0,pi] getDeltas xs =     zipWith (\(x, y) (x', y') -> getAngle (1, 0) (x' - x, y' - y)) xs (tail $   cycle xs)  getMatchingIndex :: [Double] -> [Double] -> Int getMatchingIndex xs ys = go 0 xs (ys ++ tail ys)   where     go k xs ys = if and (zipWith (\a b -> abs a - abs b <= 1e-5) xs ys)         then k         else go (k + 1) xs (tail ys)