# 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)