Line Segment Intersection

Segments intersect when they share at least one point, including endpoint touches and overlapping portions. A strict crossing test alone misses these cases. Combining orientation with point-on-segment checks gives a short exact decision algorithm for bounded integer coordinates. It is useful for path obstacles, polygon validation and geometric graph edges.

Prerequisites: Cross Product and Orientation; coordinate intervals.

Build the idea

1. Understand a proper crossing

   If neither segment endpoint lies on the other supporting line, AB and CD cross precisely when C,D lie on opposite sides of AB and A,B lie on opposite sides of CD. The two orientation pairs must each have opposite signs. Requiring both prevents a supporting-line intersection far outside one of the finite segments.

2. Define the closed boundary test

   A point P belongs to segment AB exactly when cross(A,B,P)=0 and both coordinates lie between the corresponding endpoint extrema. Both conditions matter: a collinear point can be beyond B. Coordinate min/max checks work even for vertical, horizontal and zero-length segments without division.

3. Handle special cases first

   Test whether any of the four endpoints lies on the other segment. This catches a shared endpoint, a single point touching an edge, collinear partial overlap and containment of one collinear segment in the other. If none applies, accept only a proper crossing using strict opposite signs. Two disjoint collinear segments correctly fail both stages.

4. Trace an endpoint touch

   Take AB from (0,0) to (4,0) and CD from (4,0) to (4,3). Endpoint C equals B, so on(C,A,B) is true and the answer is YES. Replacing C,D by (5,0),(7,0) produces zero determinants but no endpoint in the other range, hence NO. This contrasts collinearity with overlap.

5. Avoid hidden overflow

   Cross products fit long long for coordinates within ±10^6, but multiplying two cross values could need roughly 26 decimal digits. sign reduces each to −1,0,1 before multiplying. The function returns only existence; computing an intersection coordinate or an overlap segment is a different output task and requires additional construction logic.

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

#include<iostream>
#include<algorithm>
struct Point{
    long long x,y;
};
long long cross(Point a,Point b,Point c){
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
int sign(long long x){
    return (x>0)-(x<0);
}
bool on(Point p,Point a,Point b){
    return cross(a,b,p)==0&&std::min(a.x,b.x)<=p.x&&p.x<=std::max(a.x,b.x)&&
        std::min(a.y,b.y)<=p.y&&p.y<=std::max(a.y,b.y);
}
bool intersects(Point a,Point b,Point c,Point d){
    long long x=cross(a,b,c),y=cross(a,b,d),z=cross(c,d,a),w=cross(c,d,b);
    if(on(a,c,d)||on(b,c,d)||on(c,a,b)||on(d,a,b)){
        return true;
    }
    return sign(x)*sign(y)<0&&sign(z)*sign(w)<0; // Multiply signs, not determinants.
}
int main(){
    Point a,b,c,d;
    std::cin>>a.x>>a.y>>b.x>>b.y>>c.x>>c.y>>d.x>>d.y;
    std::cout<<(intersects(a,b,c,d)?"YES":"NO")<<'\n';
}

Complexity analysis

O(1) time and O(1) auxiliary space. A constant number of orientations and coordinate comparisons covers all cases, including degenerate point segments.

Example input and output

Read A,B,C,D as four integer pairs within ±10^6. Print YES if the two closed segments have any point in common; otherwise NO.

Input

0 0 4 0 4 0 4 3

Output

YES

The segments touch at the shared endpoint (4,0); touching counts as intersection.

Practical applications

Use for collision decisions, checking a proposed geometric edge and validating small polygons. Pairwise checking n segments costs O(n²); sweep-line algorithms can accelerate specialized or larger intersection problems.

Check your understanding

Why compare signs rather than multiplying two determinants directly?

Put it into practice

Test crossing, touching, overlapping, disjoint and two zero-length segments.