Lines and Their Equations

An infinite line can be written using a point and direction, or as ax+by+c=0. Parametric vectors avoid the vertical-line exception of y=mx+b. We derive an intersection formula from cross products, detect parallel and coincident lines exactly on bounded integer input, then compute the intersection coordinates approximately. These are building blocks for clipping and geometric constraint problems.

Prerequisites: Cross Product and Orientation; vector equations.

Build the idea

1. Relate representations

   Given distinct A,B, let u=B−A. The vector equation X=A+t·u covers the line for every real t. A perpendicular normal is (−uy,ux), producing −uy·x+ux·y+c=0 with c=uy·ax−ux·ay. Normals are useful for distances and inequalities; directions are convenient for intersections and parameter ranges.

2. Eliminate one parameter

   For a second line C+s·v, equality gives t·u−s·v=C−A. Cross both sides with v: the term cross(v,v) vanishes, leaving t·cross(u,v)=cross(C−A,v). When the denominator is nonzero, solve for t and substitute into A+t·u. This proves both existence and uniqueness in that case.

   $$X=A+\mathrm{cross}(C-A,v)/\mathrm{cross}(u,v)·u$$

3. Classify a zero denominator

   cross(u,v)=0 means parallel directions. If cross(C−A,u)=0 as well, C lies on the first line, so the lines coincide and have infinitely many intersection points. Otherwise they are distinct parallel lines and have none. Perpendicular lines satisfy dot(u,v)=0 instead; do not confuse the two tests.

4. Trace the sample

   The diagonals through (0,0)→(4,4) and (0,4)→(4,0) have u=(4,4),v=(4,−4). Their denominator is −32 and numerator −16, so t=0.5. Substitution yields (2,2). These are infinite lines; an intersection beyond an endpoint is still valid here, unlike segment intersection.

5. Implement exact predicates and approximate construction

   Integer Point coordinates within ±10^6 keep determinants safely in long long. Only after determining the exact classification does the code convert the division to long double. Identical endpoints do not define a line and produce INVALID LINE. Near-parallel lines can have very distant intersections and amplify numerical errors, so six decimal digits are a display format rather than an accuracy certificate.

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

#include<iostream>
#include<iomanip>
#include<cmath>
struct Point{
    long long x,y;
    Point operator-(Point b)const{
        return {x-b.x,y-b.y};
    }
};
long long cross(Point a,Point b){
    return a.x*b.y-a.y*b.x;
}
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;
    Point u=b-a,v=d-c,w=c-a;
    if((u.x==0&&u.y==0)||(v.x==0&&v.y==0)){
        std::cout<<"INVALID LINE\n";
        return 0;
    }
    long long denominator=cross(u,v);
    if(denominator==0){
        std::cout<<(cross(w,u)==0?"COINCIDENT":"PARALLEL")<<'\n';
        return 0;
    }
    // Cross both line equations with v to eliminate its parameter.
    long double t=(long double)cross(w,v)/denominator;
    std::cout<<std::fixed<<std::setprecision(6)<<a.x+t*u.x<<' '<<a.y+t*u.y<<'\n';
}

Complexity analysis

O(1) time and O(1) auxiliary space. Predicate calculations are exact under the input bound; point construction uses floating division.

Example input and output

Read A,B,C,D as four integer coordinate pairs within ±10^6. Print intersection coordinates to six decimals, PARALLEL, COINCIDENT or INVALID LINE.

Input

0 0 4 4 0 4 4 0

Output

2.000000 2.000000

The parameter on the first line is one half, meeting the other diagonal at (2,2).

Practical applications

Use line intersections for polygon clipping, circumcenters and arrangements. Segment intersection adds bounded-coordinate tests. A half-plane adds an allowed side to a directed line, leading to feasible-region algorithms.

Check your understanding

What distinguishes coincident lines from distinct parallel lines?

Put it into practice

Test two vertical lines, the same line with reversed endpoints, and identical endpoint input.