Algorithm in A..Z - 선분 교차 판별

개념

CCW 알고리즘을 이용하여 두 선분이 교차하는지 판별할 수 있다.

---

작동원리

위 예시를 보면 CCW(A, B, C)와 CCW(A, B, D)가 반대방향(곱이 음수)이면 두 선분은 교차한다고 볼 수 있다.

하지만 위 예시와 같은 반례가 존재한다. (직선이 아닌 선분이기 때문에 CCW의 방향이 반대여도 교차하지 않을 경우가 있다.)

그렇기 때문에 CCW(A, B, C)와 CCW(A, B, D)의 방향, CCW(C, D, A)와 CCW(C, D, B)의 방향 두 번을 검사하여 교차하는지 확인할 수 있다.

 

하지만 두 선분이 같은 직선에 있을 경우 CCW가 0이 나온다.

 

 

위와 같은 반례는 CCW(A, B, C) * CCW(A, B, D) == 0 && CCW(C, D, A) * CCW(C, D, B) == 0일 때 C가 A, B사이에 있거나 B가 C, D 사이에 있는지 확인하면 된다.

---

시간 복잡도

O(1)

---

문제

www.acmicpc.net/problem/17387

17387번: 선분 교차 2

---

코드

#include <bits/stdc++.h>
using namespace std;

constexpr int COUNTER_CLOCK_WISE = 1;
constexpr int CLOCK_WISE = -1;
constexpr int STRAIGHT = 0;

class Point {
public:
    long long x, y;

    explicit Point(long long x = 0, long long y = 0) : x(x), y(y) {

    }

    bool operator==(const Point &other) const {
        return x == other.x && y == other.y;
    }

    bool operator!=(const Point &other) const {
        return x != other.x || y != other.y;
    }

    bool operator<(const Point &other) const {
        if (x != other.x) {
            return x < other.x;
        }

        return y < other.y;
    }

    bool operator<=(const Point &other) const {
        return operator==(other) || operator<(other);
    }

    friend istream& operator>>(istream &in, Point &p) {
        return in >> p.x >> p.y;
    }

    friend ostream& operator<<(ostream &out, Point &p) {
        return out << "(" << p.x << ", " << p.y << ")";
    }
};

class Edge {
public:
    Point p1, p2;

    explicit Edge(Point p1 = Point(), Point p2 = Point()) : p1(p1), p2(p2) {

    }

    friend istream& operator>>(istream &in, Edge &e) {
        return in >> e.p1 >> e.p2;
    }

    friend ostream& operator<<(ostream &out, Edge &e) {
        return out << "(" << e.p1 << ", " << e.p2 << ")";
    }
};

int ccw(const Point &p1, const Point &p2, const Point &p3) {
    long long q1 = p1.x*p2.y + p2.x*p3.y + p3.x*p1.y;
    long long q2 = p2.x*p1.y + p3.x*p2.y + p1.x*p3.y;

    if (q1 - q2 > 0) {
        return COUNTER_CLOCK_WISE;
    } else if (q1 - q2 < 0) {
        return CLOCK_WISE;
    } else {
        return STRAIGHT;
    }
}

bool isOverlap(Edge e1, Edge e2) {
    long long q1 = ccw(e1.p1, e1.p2, e2.p1)*ccw(e1.p1, e1.p2, e2.p2);
    long long q2 = ccw(e2.p1, e2.p2, e1.p1)*ccw(e2.p1, e2.p2, e1.p2);

    if (q1 == 0 && q2 == 0) {
        if(e1.p2 < e1.p1) {
            swap(e1.p1, e1.p2);
        }

        if(e2.p2 < e2.p1) {
            swap(e2.p1, e2.p2);
        }

        if(e2.p1 < e1.p1) {
            swap(e1, e2);
        }

        return e2.p1 <= e1.p2;
    }

    return q1 <= 0 && q2 <= 0;
}

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

    Edge e1, e2;
    cin >> e1 >> e2;
    cout << isOverlap(e1, e2) << "\n";
}