BOJ. Crossing Lines 2 (17387)

On this page

[Link] https://www.acmicpc.net/problem/17387

Idea: orientation tests and closed-segment bounds

For three points $P$, $Q$, and $R$, the sign of the cross product $(Q-P) \times (R-P)$ tells which side of the directed line $PQ$ contains $R$. A positive result means counterclockwise, a negative result clockwise, and zero means collinear.

Let the segments be $AB$ and $CD$. If $C$ and $D$ lie on strictly opposite sides of line $AB$, and $A$ and $B$ lie on strictly opposite sides of line $CD$, the segments cross properly. “Strictly opposite” matters: a zero orientation is not a proper crossing and must be handled as a boundary case.

For each zero orientation, check whether the collinear point lies inside the other segment’s closed bounding box: its x-coordinate and y-coordinate must each be between the corresponding endpoint coordinates, inclusively. This test is essential for collinear segments: lying on the same infinite line alone does not mean the finite segments overlap. The inclusive bounds accept endpoint contact and overlap, and reject separated collinear segments. Checking all four endpoint-on-segment cases also covers degenerate segments consisting of a single point.

With coordinates in $[-10^9, 10^9]$, coordinate differences have magnitude at most $2 \cdot 10^9$. Each product in the cross product is at most $4 \cdot 10^{18}$ in magnitude, and their difference is at most $8 \cdot 10^{18}$, which fits in signed 64-bit integer range. The code stores coordinates and cross products as long long.

Boundary checks:

• A proper crossing returns 1.
• Segments meeting at one endpoint return 1.
• Collinear segments with a shared endpoint or positive-length overlap return 1.
• Collinear segments with a gap return 0, even though all four points are collinear.
• A point segment on another segment returns 1; a point outside it returns 0.

C++17

#include <algorithm>
#include <iostream>

using namespace std;

struct Point {
    long long x;
    long long 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);
}

int orientation(const Point& a, const Point& b, const Point& c) {
    const long long value = cross(a, b, c);
    if (value > 0) return 1;
    if (value < 0) return -1;
    return 0;
}

bool onSegment(const Point& a, const Point& b, const Point& p) {
    return min(a.x, b.x) <= p.x && p.x <= max(a.x, b.x) &&
           min(a.y, b.y) <= p.y && p.y <= max(a.y, b.y);
}

bool intersects(const Point& a, const Point& b, const Point& c, const Point& d) {
    const int abC = orientation(a, b, c);
    const int abD = orientation(a, b, d);
    const int cdA = orientation(c, d, a);
    const int cdB = orientation(c, d, b);

    if (abC * abD < 0 && cdA * cdB < 0) return true;

    if (abC == 0 && onSegment(a, b, c)) return true;
    if (abD == 0 && onSegment(a, b, d)) return true;
    if (cdA == 0 && onSegment(c, d, a)) return true;
    if (cdB == 0 && onSegment(c, d, b)) return true;
    return false;
}

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;

    cout << (intersects(a, b, c, d) ? 1 : 0) << '\n';
    return 0;
}