July 18 ADA Training - Geometry

Triangle and point

The triangle and the point are given on the 2D coordinate plane. Is the point In, On or Out of the triangle?


The coordinates of the vertices of a triangle are given in the first 3 lines (each line contains 2 integers). The fourth line contains the point's coordinates in the same format. All numbers are integers; their absolute values are no more than 10000. The vertices of triangle do not lie on a straight line.


Print the word "In" if the point is located inside the triangle, "On" if the point lies on the border of triangle (on the vertex or on the edge), and "Out" if the point is outside the triangle.

Time limit 1 second
Memory limit 128 MiB
Input example #1
-2 -2
3 1
0 1
0 0
Output example #1