BOJ. Crossing Lines (17386)

On this page

Problem

Orientation and segment intersection

For points A, B, and C, define the signed orientation

cross(A, B, C) = (B.x - A.x)(C.y - A.y) - (B.y - A.y)(C.x - A.x)

A positive value means C is to the counterclockwise side of directed line AB; a negative value means clockwise; zero means the points are collinear.

The input gives two segments AB and CD. The problem guarantees that no three of the four endpoints are collinear. Therefore the segments cannot touch at an endpoint or lie on a common line: any intersection must be a proper crossing through the interior of both segments. The segments cross exactly when A and B lie on opposite sides of line CD, and C and D lie on opposite sides of line AB. In orientation values, both pairs must have opposite signs.

Checking both segments is important: opposite sides of only one infinite line do not by themselves prove that the finite segments intersect. The collinearity guarantee also means none of the four orientation values is zero, so strict sign comparisons are sufficient. Do not multiply the two cross products to compare signs, since that product can overflow even when each cross product fits in 64 bits.

The coordinate limits are -1,000,000 <= x, y <= 1,000,000. Coordinate differences are at most 2,000,000, so a cross product has magnitude at most 8 × 10^12, which fits in a signed 64-bit integer. The algorithm uses O(1) time and O(1) extra space.

C++17 implementation

#include <iostream>
using namespace std;

struct Point {
    long long x, y;
};

long long cross(const Point& a, const Point& b, const Point& c) {
    return (b.x - a.x) * (c.y - a.y)
         - (b.y - a.y) * (c.x - a.x);
}

bool oppositeSigns(long long a, long long b) {
    return (a < 0 && b > 0) || (a > 0 && b < 0);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    Point a, b, c, d;
    cin >> a.x >> a.y >> b.x >> b.y
        >> c.x >> c.y >> d.x >> d.y;

    const long long abC = cross(a, b, c);
    const long long abD = cross(a, b, d);
    const long long cdA = cross(c, d, a);
    const long long cdB = cross(c, d, b);

    cout << (oppositeSigns(abC, abD) && oppositeSigns(cdA, cdB));
}