Computational Geometry

from dataclasses import dataclass

@dataclass(frozen=True, order=True)
class Point:
    x: int
    y: int

def cross(a, b, c):
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)

def on_segment(a, b, p):
    return (cross(a, b, p) == 0 and
            min(a.x, b.x) <= p.x <= max(a.x, b.x) and
            min(a.y, b.y) <= p.y <= max(a.y, b.y))

def intersects(a, b, c, d):
    o1, o2 = cross(a, b, c), cross(a, b, d)
    o3, o4 = cross(c, d, a), cross(c, d, b)
    if ((o1 > 0 > o2 or o2 > 0 > o1) and
            (o3 > 0 > o4 or o4 > 0 > o3)):
        return True
    return ((o1 == 0 and on_segment(a, b, c)) or
            (o2 == 0 and on_segment(a, b, d)) or
            (o3 == 0 and on_segment(c, d, a)) or
            (o4 == 0 and on_segment(c, d, b)))

assert intersects(Point(0, 0), Point(4, 4), Point(0, 4), Point(4, 0))

import java.math.BigInteger;

public final class SegmentIntersection {
    record Point(int x, int y) {}

    static BigInteger cross(Point a, Point b, Point c) {
        long abx = (long) b.x() - a.x(), aby = (long) b.y() - a.y();
        long acx = (long) c.x() - a.x(), acy = (long) c.y() - a.y();
        return BigInteger.valueOf(abx).multiply(BigInteger.valueOf(acy))
                .subtract(BigInteger.valueOf(aby).multiply(BigInteger.valueOf(acx)));
    }

    static boolean onSegment(Point a, Point b, Point p) {
        return cross(a, b, p).signum() == 0
                && Math.min(a.x(), b.x()) <= p.x() && p.x() <= Math.max(a.x(), b.x())
                && Math.min(a.y(), b.y()) <= p.y() && p.y() <= Math.max(a.y(), b.y());
    }

    static boolean intersects(Point a, Point b, Point c, Point d) {
        int o1 = cross(a, b, c).signum(), o2 = cross(a, b, d).signum();
        int o3 = cross(c, d, a).signum(), o4 = cross(c, d, b).signum();
        if (((o1 > 0 && o2 < 0) || (o1 < 0 && o2 > 0))
                && ((o3 > 0 && o4 < 0) || (o3 < 0 && o4 > 0))) return true;
        return (o1 == 0 && onSegment(a, b, c)) || (o2 == 0 && onSegment(a, b, d))
                || (o3 == 0 && onSegment(c, d, a)) || (o4 == 0 && onSegment(c, d, b));
    }

    public static void main(String[] args) {
        Point a = new Point(0, 0), b = new Point(4, 4);
        Point c = new Point(0, 4), d = new Point(4, 0);
        if (!intersects(a, b, c, d)) throw new AssertionError();
        if (cross(a, b, new Point(2, 2)).signum() != 0) throw new AssertionError();
        Point min = new Point(Integer.MIN_VALUE, Integer.MIN_VALUE);
        Point max = new Point(Integer.MAX_VALUE, Integer.MAX_VALUE);
        if (cross(min, max, new Point(Integer.MIN_VALUE, Integer.MAX_VALUE)).signum() <= 0) {
            throw new AssertionError("full-range coordinates must not overflow");
        }
    }
}