Information

Deadline No deadline
Submission limit No limitation

Sign in

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}\).


geometry-orient/products5.png

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.

geometry-orient/products7.png

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.0 MiB
Allowed extensions: .java, .cpp, .py