Geometry - Point orientation

One of the main uses of cross product is in determining the relative position of points and other objects. For this, we define the function $$orient(A, B, C) = \vec{AB} \times \vec{AC}$$. It is positive if $$C$$ is on the left side of $$\vec{AB}$$, negative on the right side, and zero if $$C$$ is on the line containing $$\vec{AB}$$. It is straightforward to implement:

// create the vector from point a to point b
static Point vec(Point a, Point b) {
return new Point(b.x - a.x, b.y - a.y);
}

static double orient(Point a, Point b, Point c) {
return cross(vec(a, b), vec(a, c));
}


In most situations we only care about the sign of $$orient(a, b, c)$$. Therefore we define a function $$sorient(a, b, c)$$ which returns the sign of $$orient(a, b, c)$$

\begin{equation*} sorient(a, b, c) = \begin{cases} 1 & \quad orient(a, b, c) > 0 \\ 0 & \quad orient(a, b, c) = 0 \\ -1 & \quad orient(a, b, c) < 0 \end{cases} \end{equation*}
static double sorient(Point a, Point b, Point c) {
double o = orient(a, b, c);
return o < 0 ? -1 : o > 0 ? 1 : 0;
}


Point in angle

As an example of use of the orientation of three points, write an function to check whether a point $$P$$ lies strictly inside the angle formed by two semi-lines $$AB$$ and $$AC$$.

For instance, in the following figure, in the first two cases the point $$P$$ does not lie inside the angle and in the last case it does. Note: Do not make any assumptions on the orientation of the input points $$A$$, $$B$$ and $$C$$. However you can assume that they are not collinear.

Input

• One line with two integers $$A_x, A_y$$ giving the coordiantes of point $$A$$.
• One line with two integers $$B_x, B_y$$ giving the coordiantes of point $$B$$.
• One line with two integers $$C_x, C_y$$ giving the coordiantes of point $$C$$.
• One line with two integers $$P_x, P_y$$ giving the coordiantes of point $$P$$.

Constraints

• $$-10^5 \leq A_x, A_y, B_x, B_y, C_x, C_y, P_x, P_y \leq 10^5$$

Output

A single line with yes if $$P$$ lies in the angle formed by two semi-lines $$AB$$ and $$AC$$ and no otherwise.

Sample Test Cases

Sample input 1

Sample output 1

Sample input 2

Sample output 2

Sample input 3

Sample output 3

Max file size: 1.0MB
Allowed extensions: .java, .cpp, .py