17387(선분 교차2)

난이도: 골드 2

 

https://www.acmicpc.net/problem/17387

17387번: 선분 교차 2

 

문제

2차원 좌표 평면 위의 두 선분 L1, L2가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있는 것도 교차하는 것이다.

L1의 양 끝 점은 (x1, y1), (x2, y2), L2의 양 끝 점은 (x3, y3), (x4, y4)이다.

입력

첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다.

출력

L1과 L2가 교차하면 1, 아니면 0을 출력한다.

제한

• -1,000,000 ≤ x1, y1, x2, y2, x3, y3, x4, y4 ≤ 1,000,000
• x1, y1, x2, y2, x3, y3, x4, y4는 정수
• 선분의 길이는 0보다 크다.

풀이

#include <iostream>
#include <algorithm>
using namespace std;

struct Point {
    double x, y;
    Point() {}
    Point(double x, double y) : x(x), y(y) {}
    Point operator - (const Point& a) const {
        return Point(x - a.x, y - a.y);
    }
    double operator * (const Point& a) const {
        return x * a.y - y * a.x;
    }
    bool operator > (const Point& a) const {
        if (x != a.x)
            return x > a.x;
        return y > a.y;
    }
    bool operator <= (const Point& a) const {
        if (x != a.x)
            return x < a.x;
        return y <= a.y;
    }
};

int ccw(Point p1, Point p2, Point p3) {
    double res = (p2 - p1) * (p3 - p2);
    if (res > 0) return 1; // 반시계 방향
    else if (res < 0) return -1; // 시계 방향
    else return 0; // 일직선
}

bool isIntersect(Point p1, Point p2, Point p3, Point p4) {
    // 선분이 교차하려면,
    // (한 선분에서 다른 선분의 점으로 ccw를 할 때 하나는 좌회전, 다른 하나는 우회전을 해야 함)
    // ccw(p1, p2, p3) * ccw(p1, p2 ,p4) 음수 
    // ccw(p3, p4, p1) * ccw(p3, p4, p2) 음수
    int ccw1 = ccw(p1, p2, p3) * ccw(p1, p2, p4);
    int ccw2 = ccw(p3, p4, p1) * ccw(p3, p4, p2);
    if (ccw1 == 0 && ccw2 == 0) {   
        // 직선상에 놓여있을 때, 점이 겹치거나 선분 위에 있는지 체크
        if (p1 > p2) swap(p1, p2);
        if (p3 > p4) swap(p3, p4);
        return p3 <= p2 && p1 <= p4;
    }
    return ccw1 <= 0 && ccw2 <= 0;
}

int main() {
    Point p1, p2, p3, p4;
    cin >> p1.x >> p1.y >> p2.x >> p2.y >> p3.x >> p3.y >> p4.x >> p4.y;

    cout << isIntersect(p1, p2, p3, p4);
}