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

2099. Space Invader

Time limit: 1.0 second
Memory limit: 64 MB
Winter in Yekaterinburg is the longest time of the year. And everyone spends long winter evenings in his own way. For example, Eugene creates computer games in the evenings. His current game has a very simple game play — user controls a spaceship flying in 3D space. To test the mechanics of the movement of his spaceship Eugene wants to solve the following problem: can his spaceship, moving in a straight line, fly through the points A and B, then make a turn at 90°, and then fly through the points C and D, continuing to move in a straight line. The points A, B, C, D should be visited by the spaceship in just that order, the turning point may coincide with the point B or the point C. The spaceship should be considered as a material point.


There are four lines, each containing integers xi, yi, zi that are the coordinates of the points A, B, C, D respectively (−106xi, yi, zi ≤ 106). All points are pairwise different.


If the spaceship can fly through the data points, output “Valid”, otherwise output “Invalid”.


-2 0 0
-1 0 0
0 1 0
0 2 0
Problem Author: Denis Dublennykh
Problem Source: Open Ural FU Personal Contest 2014