"""
Given two line segments, determine whether they intersect.

This is based on the algorithm described in Introduction to Algorithms
(CLRS), Chapter 33.

Reference:
    - https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection
    - https://en.wikipedia.org/wiki/Orientation_(geometry)
"""

from __future__ import annotations

from typing import NamedTuple


class Point(NamedTuple):
    """A point in 2D space.

    >>> Point(0, 0)
    Point(x=0, y=0)
    >>> Point(1, -3)
    Point(x=1, y=-3)
    """

    x: float
    y: float


def direction(pivot: Point, target: Point, query: Point) -> float:
    """Return the cross product of vectors (pivot->query) and (pivot->target).

    The sign of the result encodes the orientation of the ordered triple
    (pivot, target, query):
      - Negative  ->  counter-clockwise (left turn)
      - Positive  ->  clockwise (right turn)
      - Zero      ->  collinear

    >>> direction(Point(0, 0), Point(1, 0), Point(0, 1))
    -1
    >>> direction(Point(0, 0), Point(0, 1), Point(1, 0))
    1
    >>> direction(Point(0, 0), Point(1, 1), Point(2, 2))
    0
    """
    return (query.x - pivot.x) * (target.y - pivot.y) - (target.x - pivot.x) * (
        query.y - pivot.y
    )


def on_segment(seg_start: Point, seg_end: Point, point: Point) -> bool:
    """Check whether *point*, known to be collinear with the segment, lies on it.

    >>> on_segment(Point(0, 0), Point(4, 4), Point(2, 2))
    True
    >>> on_segment(Point(0, 0), Point(4, 4), Point(5, 5))
    False
    >>> on_segment(Point(0, 0), Point(4, 0), Point(2, 0))
    True
    """
    return min(seg_start.x, seg_end.x) <= point.x <= max(
        seg_start.x, seg_end.x
    ) and min(seg_start.y, seg_end.y) <= point.y <= max(seg_start.y, seg_end.y)


def segments_intersect(p1: Point, p2: Point, p3: Point, p4: Point) -> bool:
    """Return True if line segment p1p2 intersects line segment p3p4.

    Uses the CLRS cross-product / orientation method.  Handles both the
    general case (proper crossing) and degenerate cases where one endpoint
    lies exactly on the other segment.

    >>> segments_intersect(Point(0, 0), Point(2, 2), Point(0, 2), Point(2, 0))
    True
    >>> segments_intersect(Point(0, 0), Point(2, 2), Point(1, 1), Point(3, 3))
    True
    >>> segments_intersect(Point(0, 0), Point(1, 0), Point(2, 0), Point(3, 0))
    False
    >>> segments_intersect(Point(0, 0), Point(1, 1), Point(1, 0), Point(2, 1))
    False
    >>> segments_intersect(Point(0, 0), Point(1, 1), Point(0, 1), Point(0, 2))
    False
    >>> segments_intersect(Point(0, 0), Point(1, 0), Point(1, 0), Point(2, 0))
    True
    """
    d1 = direction(p3, p4, p1)
    d2 = direction(p3, p4, p2)
    d3 = direction(p1, p2, p3)
    d4 = direction(p1, p2, p4)

    if ((d1 < 0 < d2) or (d2 < 0 < d1)) and ((d3 < 0 < d4) or (d4 < 0 < d3)):
        return True

    if d1 == 0 and on_segment(p3, p4, p1):
        return True
    if d2 == 0 and on_segment(p3, p4, p2):
        return True
    if d3 == 0 and on_segment(p1, p2, p3):
        return True
    return d4 == 0 and on_segment(p1, p2, p4)


if __name__ == "__main__":
    import doctest

    doctest.testmod()

    print("Enter four points as 'x y' pairs (one per line):")
    points = [Point(*map(float, input().split())) for _ in range(4)]
    p1, p2, p3, p4 = points
    result = segments_intersect(p1, p2, p3, p4)
    print(1 if result else 0)