Cross Product and Orientation

Orientation is the central yes/no primitive of planar geometry: does walking A→B→C make a left turn, a right turn, or no turn? The two-dimensional cross product answers using a determinant. It powers segment intersection, polygon area and convex hulls. This lesson uses exact bounded integer arithmetic and avoids slope division, so vertical lines require no special formula.

Prerequisites: Points and Vectors; integer ranges.

Build the idea

1. Translate to vectors

   Construct u=B−A and v=C−A. Using the same origin A makes the result invariant under translating the whole configuration. The scalar cross product ux·vy−uy·vx is the signed area of the parallelogram spanned by these vectors. The triangle’s signed doubled area is the same value.

2. Interpret the sign

   In a coordinate system with y upward, positive cross means counterclockwise, so C lies left of the directed line A→B. Negative means clockwise/right. Zero means the three points are collinear, including coincident-point cases. Reversing A and B reverses the sign without changing collinearity. Collinearity alone does not say C is between the endpoints.

   $$\mathrm{cross}(B-A,C-A)=(\mathrm{bx}-\mathrm{ax})(\mathrm{cy}-\mathrm{ay})-(\mathrm{by}-\mathrm{ay})(\mathrm{cx}-\mathrm{ax})$$

3. Work a determinant

   With A=(1,1),B=(4,1),C=(2,3), u=(3,0) and v=(1,2). The determinant is 3·2−0·1=6, hence a left turn and triangle area 3. The displayed coordinates themselves form a small visual example: AB is horizontal to the right and C is two units above it.

4. Bound intermediate arithmetic

   Each coordinate is within ±10^6. Differences are at most 2·10^6; each product is at most 4·10^12 in magnitude and their difference at most 8·10^12, safely within signed long long. These deliberately conservative bounds prove safety before running. For unrestricted 64-bit coordinates even __int128 may need careful difference bounds; changing the type name is not a complete proof.

5. Reuse a predicate, not a picture

   The cross function returns the determinant; main maps its sign to a readable classification. Later algorithms should reuse this single convention rather than inventing different left-turn definitions. Integer input does not need an epsilon: treating small nonzero integer determinants as zero would destroy exact distinctions. Floating-point inputs require a separately justified tolerance or robust predicates.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
struct Point{
    long long x,y;
};
long long cross(Point a,Point b,Point c){
    // Differences <=2*10^6; determinant magnitude <=8*10^12.
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
int main(){
    Point a,b,c;
    std::cin>>a.x>>a.y>>b.x>>b.y>>c.x>>c.y;
    // Positive means C lies on the left of directed A -> B (Cartesian Y upward).
    long long turn=cross(a,b,c);
    std::cout<<turn<<'\n'
                <<(turn>0?"COUNTERCLOCKWISE"
                            :turn<0?"CLOCKWISE"
                                    :"COLLINEAR")
                <<'\n';
}

Complexity analysis

O(1) time and O(1) auxiliary space, with a constant number of safe integer operations.

Example input and output

Read ax ay bx by cx cy, all integers within ±10^6. Print the signed cross product and COUNTERCLOCKWISE, CLOCKWISE or COLLINEAR.

Input

1 1 4 1 2 3

Output

6
COUNTERCLOCKWISE

The base vector is (3,0) and C−A is (1,2), so the determinant is 6.

Practical applications

Use orientation for hull turns, segment intersection, polygon inclusion and half-plane membership. Dot products answer alignment and projection questions; orientation distinguishes the two sides of a directed boundary.

Check your understanding

What additional test is needed after collinearity to put C on segment AB?

Put it into practice

Swap A and B and predict the new output before running.