2278. Inside, On the Edge, or Outside the Triangle

A non-degenerate triangle A B C is given, then q query points. For each, print IN if it is strictly inside the triangle, ON if it lies on an edge or at a vertex, and OUT otherwise.

triangle (0,0) (4,0) (0,4) (1,1) -> IN (2,0) -> ON on the bottom edge (0,0) -> ON at a vertex (5,5) -> OUT (1,3) -> ON on the sloping edge, since 1 + 3 = 4

## What most people try first

Comparing areas: compute the area of ABC and the three areas PBC, APC, ABP, and declare the point inside when the three add up to the whole. That is correct in exact arithmetic and it is a trap in floating point, because the test becomes "do these three approximations sum to that approximation", which needs a tolerance and gets the ON cases wrong in both directions.

The same idea done with doubled integer areas works and is more arithmetic than needed.

## Three orientation tests with a shared sign

If the triangle is listed ANTICLOCKWISE, then a point inside it is to the LEFT of all three directed edges A->B, B->C and C->A. So:

``` s1 = orientation of (A, B, P) s2 = orientation of (B, C, P) s3 = orientation of (C, A, P)

any of them negative -> OUT any of them zero -> ON all three positive -> IN ```

Each orientation is #2271's cross product sign. The order of the two tests matters: a point can be on the LINE of one edge while being outside the triangle across another, so OUT has to be checked before ON. Checking ON first would report a point like (5,0) on the extension of the bottom edge as being on the triangle. The declared test (0,0) (2,0) (1,2) with the query (0,1) covers that: it is on no edge and outside, and a wrong ordering of the tests changes nothing there, whereas the query (1,2) is a vertex and must be ON.

## Normalising the winding first

The three-positive rule assumes an anticlockwise listing. The input makes no such promise, so normalise:

if cross(A, B, C) < 0: swap B and C

After that the triangle is anticlockwise and the rule applies. The alternative, accepting "all three the same sign", also works and makes the zero case harder to state: with a mixture of zeros and one sign you have to decide whether the zeros count as agreeing. Normalising first keeps the three cases crisp.

The triangle is guaranteed non-degenerate, so cross(A, B, C) is never zero and the swap is well defined. A degenerate triangle has no interior and every classification would collapse to ON or OUT, which is a different problem.

## Why this is the right first step toward point-in-polygon

For a triangle, three orientation tests settle it. For a general polygon they do not, because a point can be to the left of some edges and to the right of others and still be inside a non-convex shape. #2293 is where that is dealt with, by ray casting. For a CONVEX polygon the "same side of every edge" rule does generalise, and this problem is that rule at its smallest size.

## Width

Coordinates satisfy |x|, |y| <= 10^6, so each cross product is at most 8 * 10^12 in magnitude and needs a 64-bit integer. A signed 32-bit one stops at 2147483647 and a wrapped cross product can change SIGN, which turns an IN into an OUT with no sign of trouble.

Only signs are used, so nothing accumulates and no sum can overflow. In JavaScript the values are below 2^53 = 9007199254740992 and a plain Number is exact.

Constraints - `1 ≤ q ≤ 100000` - `-1000000 ≤ every coordinate ≤ 1000000` - the triangle is non-degenerate, so its three vertices are not collinear - the vertices may be listed in either winding order