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 2015

About     Problems     Submit solution     Judge status     Standings
Contest is over

E. 3D-modeling

Time limit: 1.0 second
Memory limit: 64 MB
Android Vasya’s elder friends have already been modeling six-dimensional space ships for quite a long time. Vasya himself hasn’t yet acquired such level of mastering. He has only just started the 3d-modeling course. And right now he is doing his first homework.
The homework is pretty easy, one just needs to make a 3d-drawing of any detail. Vasya has already come up with the detail he wants to draw, imagined how it would look like and he even has drawn the first straight line. But something went wrong. Apparently the line turned out to be not the one he needed.
But Vasya has already got the solution for this problem. He plans to rotate the detail in his mind in such a way, that the line he was going to draw would become the line he had actually drawn. Help Vasya find out what rotation he should make for this.


First two lines contain coordinates of the points A and B. These points lie on the drawn line. The third and the fourth lines contain coordinates of the points C and D. These points lie on the line Vasya was going to draw. Point A doesn’t coincide with point B, point C doesn’t coincide with point D. All numbers in the input data are integers and do not exceed 1000 by absolute value.


If the required rotation doesn’t exist output “Impossible” in a single line. Otherwise in the first two lines output coordinates of the points P and Q which lie on the rotation axis. In the third line output the rotation angle α in degrees. The distance between points P and Q should not be less than 1. The coordinates of points P and Q should not exceed 2000 by absolute value. The angle should lie within the range [0; 360] and be counted counterclockwise, if one is looking from P to the direction of Q. An answer is considered correct if after rotation of the line CD by the angle α around the axis PQ it results in some line EF, such that the distances from points A and B to this line EF don’t exceed 10−5.


0 0 0
0 1 0
0 0 0
1 0 0
0 0 1
0 0 0
1 0 1
1 0 0
0 1 1
0 1 0
0 0 1
0 0 0
Problem Author: Egor Shchelkonogov (idea by Dmitry Ivankov)
Problem Source: Ural Sport Programming Championship 2015
To submit the solution for this problem go to the Problem set: 2050. 3D-modeling