Line Segments Intersection [GeeksforGeeks]

Given two line segments (p1, q1) and (p2, q2), find if the given line segments intersect with each other. [Check here for problem statement and here for background information]

Two segments (p1,q1) and (p2,q2) intersect if and only if one of the following two conditions is verified: [from GeeksforGeeks]
1. General Case:
- (p1, q1, p2) and (p1, q1, q2) have different orientations AND
- (p2, q2, p1) and (p2, q2, q1) have different orientations
OR
2. Special Case
- (p1, q1, p2), (p1, q1, q2), (p2, q2, p1), and (p2, q2, q1) are all collinear and
- the x-projections of (p1, q1) and (p2, q2) intersect
- the y-projections of (p1, q1) and (p2, q2) intersect

#include <iostream>

using namespace std;

struct Point{
    int x, y;
    Point(int a, int b):x(a),y(b){}
};

//Given 3 colinear pointers p, q and r; Determine if r is on the segment pq
bool onSegment(Point p, Point q, Point r){
    return r.x<=max(p.x, q.x)&&r.x>=min(p.x, q.x)&&
           r.y<=max(p.y, q.y)&&r.y>=min(p.y, q.y);
} 

//Calculate the orientation of segments pq, and qr
int orientation(Point p, Point q, Point r){
    int o = (q.y-p.y)*(r.x-q.x)-
        (r.y-q.y)*(q.x-p.x);
    if (o==0)
        return 0; //colinear
    return o>0?1:-1; //clockwise and counterclockwise
}

bool doIntersect(Point p1, Point q1, Point p2, Point q2){
    int d1=orientation(p1, q1, p2);
    int d2=orientation(p1, q1, q2);
    int d3=orientation(p2, q2, p1);
    int d4=orientation(p2, q2, q1);

    // General case
    if(d1!=d2 && d3!=d4)
        return true;
    //Special case
    if(d1==0 && onSegment(p1, q1, p2))
        return true;
    if(d2==0 && onSegment(p1, q1, q2))
        return true;
    if(d3==0 && onSegment(p2, q2, p1))
        return true;
    if(d4==0 && onSegment(p2, q2, q1))
        return true;
    return false;
}

int main(){
    struct Point p1 = {1, 1}, q1 = {10, 1};
    struct Point p2 = {1, 2}, q2 = {10, 2};

    doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n";

    p1 = {10, 0}, q1 = {0, 10};
    p2 = {0, 0}, q2 = {10, 10};
    doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n";

    p1 = {-5, -5}, q1 = {0, 0};
    p2 = {1, 1}, q2 = {10, 10};
    doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n";
    return 0;
}