// C++ Program to find the intersection point of two lines

#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;

// Structure to represent a point in 2D space
struct Point {
    // x and y coordinates of the point
    double x, y;
};

// Function to check if a point lies on a given line segment
bool onSegment(Point p, Point q, Point r)
{
    if (q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x)
        && q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y))
        return true;
    return false;
}

// Function to find the orientation of the ordered triplet
// (p, q, r) 0 -> p, q and r are collinear 1 -> Clockwise 2
// -> Counterclockwise
int orientation(Point p, Point q, Point r)
{
    double val = (q.y - p.y) * (r.x - q.x)
                 - (q.x - p.x) * (r.y - q.y);
    if (val == 0)
        // collinear
        return 0;
    // clock or counterclock wise
    return (val > 0) ? 1 : 2;
}

// Function to check if two lines (p1q1 and p2q2) intersect
bool doIntersect(Point p1, Point q1, Point p2, Point q2,
                 Point& intersection)
{
    // Find the four orientations needed for general and
    // special cases
    int o1 = orientation(p1, q1, p2);
    int o2 = orientation(p1, q1, q2);
    int o3 = orientation(p2, q2, p1);
    int o4 = orientation(p2, q2, q1);

    // General case: lines intersect if they have different
    // orientations
    if (o1 != o2 && o3 != o4) {
        // Compute intersection point
        double a1 = q1.y - p1.y;
        double b1 = p1.x - q1.x;
        double c1 = a1 * p1.x + b1 * p1.y;

        double a2 = q2.y - p2.y;
        double b2 = p2.x - q2.x;
        double c2 = a2 * p2.x + b2 * p2.y;

        double determinant = a1 * b2 - a2 * b1;

        if (determinant != 0) {
            intersection.x
                = (c1 * b2 - c2 * b1) / determinant;
            intersection.y
                = (a1 * c2 - a2 * c1) / determinant;
            return true;
        }
    }

    // Special Cases: check if the lines are collinear and
    // overlap
    if (o1 == 0 && onSegment(p1, p2, q1))
        return true;
    if (o2 == 0 && onSegment(p1, q2, q1))
        return true;
    // Lines do not intersect in any case
    return false;
}

int main()
{
    // Define first line segment
    Point p1 = { 2, 3 }, q1 = { 5, 7 };
    // Define second line segment
    Point p2 = { 3, 9 }, q2 = { 6, 2 };
    // Point to store the intersection
    Point intersection;

    // Check if the lines intersect and print the result
    if (doIntersect(p1, q1, p2, q2, intersection)) {
        cout << "The lines intersect at point ("
             << intersection.x << ", " << intersection.y
             << ")." << endl;
    }
    else {
        cout << "The lines do not intersect within the "
                "segments."
             << endl;
    }

    return 0;
}