line_segment_intersection.cpp

/**
 * @file
 * @brief check whether two line segments intersect each other
 * or not.
 */
#include <algorithm>
#include <iostream>

/**
 * Define a Point.
 */
struct Point {
    int x;  /// Point respect to x coordinate
    int y;  /// Point respect to y coordinate
};

/**
 * intersect returns true if segments of two line intersects and
 * false if they do not. It calls the subroutines direction
 * which computes the orientation.
 */
struct SegmentIntersection {
    inline bool intersect(Point first_point, Point second_point,
                          Point third_point, Point forth_point) {
        int direction1 = direction(third_point, forth_point, first_point);
        int direction2 = direction(third_point, forth_point, second_point);
        int direction3 = direction(first_point, second_point, third_point);
        int direction4 = direction(first_point, second_point, forth_point);

        if ((direction1 < 0 || direction2 > 0) &&
            (direction3 < 0 || direction4 > 0))
            return true;

        else if (direction1 == 0 &&
                 on_segment(third_point, forth_point, first_point))
            return true;

        else if (direction2 == 0 &&
                 on_segment(third_point, forth_point, second_point))
            return true;

        else if (direction3 == 0 &&
                 on_segment(first_point, second_point, third_point))
            return true;

        else if (direction3 == 0 &&
                 on_segment(first_point, second_point, forth_point))
            return true;

        else
            return false;
    }

    /**
     * We will find direction of line here respect to @first_point.
     * Here @second_point and @third_point is first and second points
     * of the line respectively. we want a method to determine which way a
     * given angle these three points turns. If returned number is negative,
     * then the angle is counter-clockwise. That means the line is going to
     * right to left. We will fount angle as clockwise if the method returns
     * positive number.
     */
    inline int direction(Point first_point, Point second_point,
                         Point third_point) {
        return ((third_point.x - first_point.x) *
                (second_point.y - first_point.y)) -
               ((second_point.x - first_point.x) *
                (third_point.y - first_point.y));
    }

    /**
     * This method determines whether a point known to be colinear
     * with a segment lies on that segment.
     */
    inline bool on_segment(Point first_point, Point second_point,
                           Point third_point) {
        if (std::min(first_point.x, second_point.x) <= third_point.x &&
            third_point.x <= std::max(first_point.x, second_point.x) &&
            std::min(first_point.y, second_point.y) <= third_point.y &&
            third_point.y <= std::max(first_point.y, second_point.y))
            return true;

        else
            return false;
    }
};

/**
 * This is the main function to test whether the algorithm is
 * working well.
 */
int main() {
    SegmentIntersection segment;
    Point first_point, second_point, third_point, forth_point;

    std::cin >> first_point.x >> first_point.y;
    std::cin >> second_point.x >> second_point.y;
    std::cin >> third_point.x >> third_point.y;
    std::cin >> forth_point.x >> forth_point.y;

    printf("%d", segment.intersect(first_point, second_point, third_point,
                                   forth_point));
    std::cout << std::endl;
}