ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural Championship 2013

About     Problems     Submit solution     Judge status     Standings
Contest is over

E. Model of the Earth

Time limit: 1.0 second
Memory limit: 64 MB
‘Is it a model of the Solar system?’
‘Yes, I’ve just made it. Look, all the planets rotate around the Sun, and some of them also rotate around their own axes.’
‘And why does the Earth’s axis go through Singapore and Ecuador?’
‘That’s what I’m trying to fix right now. You see, I have two models of the Earth. Both of them are spheres. The first model is physical. I use it to calculate the rotation of the Earth around its axis and around the Sun and the influence of the Moon and other celestial bodies. The second model is graphical. It’s shown on the screen with continents and oceans. These two models have been superposed incorrectly, and now the North Pole is in Singapore.’
‘How did you superpose the models?’
‘Very simply. I chose several key points on the graphical model and specified their places on the physical model. Then the graphical engine found the rotation that should be applied to one model to make the key points coincide with the key points on the other model. But the engine doesn’t know the right correspondence between the key points on the models. Now the key points coincide but not in the way I want.’
‘Do you know the number of different rotations of the sphere for which all the key points go into key points?’
‘That’s an interesting question, let’s find it.’


The first line contains the number n of key points on the sphere (3 ≤ n ≤ 200). Each of the following n lines contains real numbers xi, yi, and zi, which are the coordinates of the i-th key point in a Cartesian coordinate system with origin at the center of the Earth. The coordinates are given in Earth radius units with at most nine fractional digits. The distance between any two key points is at least 10−5 units.


Output the number of rotations of the sphere that map every key point to a key point, including the identity rotation. You should consider a rotation to map a key point A to a key point B if A is mapped to a point within 10−6 units distance from the point B. Rotations having the same mapping should be considered as the same rotation.


0 1 0
1 0 0
0 0 1
Problem Author: Denis Dublennykh
Problem Source: Ural Sport Programming Championship 2013
To submit the solution for this problem go to the Problem set: 1975. Model of the Earth