‘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.’
Input
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
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.
Sample
input | output |
---|
3
0 1 0
1 0 0
0 0 1
| 3
|
Problem Author: Denis Dublennykh
Problem Source: Ural Sport Programming Championship 2013