선분 교차 판별

두 선분이 주어질 때 선분의 교차를 판별하는 법에 대해서 알아보자.

각 선분은 2개의 정점으로 주어질 것이다.

각 선분을 가지고 다른 선분과 ccw를 돌린다. 

ccw(선분 하나와 다른선분의 정점) * ccw(선분 하나와 다른 선분의 다른 정점) <=0 and ccw(다른 선분과 선분 하나의 정점) * ccw(다른 선분과 선분 하나의 다른 정점) <=0

등호는 선분이 서로 관통하지는 않고 딱 만났을 경우이다. 여기서는 이 경우 또한 교차했다고 본다.

위의 조건까지 성립하게 되면, 물리적으로는 아니지만 두 선분이 이루는 각도 상으로는 만날 수 있는 조건을 충족한다.

선분이 아니라 직선이었다면 위의 조건까지만 충족해도 만나는 것이다. 하지만 선분이기 때문에, 어떻게 놓여있느냐에 따라서 만날 수도 있고 아닐 수도 있다.

선분 하나의 두 x좌표가 다른 선분의 두 x좌표보다 모두 작거나, y좌표 또한 이렇다면 두 선분은 만나지 못한다. 이를 코드로 표현하면 다음과 같다.

(ccw, isCross 함수를 보면 된다. main에서 특별히 뭘 하는 건 없음)

#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
typedef long long ll;
struct LINE {
    int x1, y1, x2, y2;
 
};
LINE L[3001];
 
 
ll ccw(int x1, int y1, int x2, int y2, int x3, int y3) { 
    ll ret = (x1*y2 + x2*y3 +x3*y1) - (y1*x2 + y2*x3 + y3*x1);
    if (ret < 0) return -1;
    else if (ret > 0) return 1;
    else return 0;
}
 
bool isCross(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
    //만나면 true, 아니면 false -> 선분 ccw 곱의 결과가 음수이지만 안 만나는 경우
    //예외 처리 필요 -> 0인 경우도 예외 처리에 포함시켜야함(평행이동 하면 관통안하고 만나기만하는 경우)
    if (ccw(x1, y1, x2, y2, x3, y3) * ccw(x1, y1, x2, y2, x4, y4) <= 0 &&
        ccw(x3, y3, x4, y4, x1, y1) * ccw(x3, y3, x4, y4, x2, y2) <= 0) {
        //여기까지 보면 각소 상으로는 만날 수 있는 조건을 갖춤
        if ((x1 > x3 && x1 > x4 && x2 > x3 && x2 > x4) ||
            (x3 > x1 && x3 > x2 && x4 > x1 && x4 > x2)) return false;
        else if ((y1 > y3 && y1 > y4 && y2 > y3 && y2 > y4) ||
            (y3 > y1 && y3 > y2 && y4 > y1 && y4 > y2)) return false;
        else
            return true;
    }
    return false; //애초에 양수면 교차X
}
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> L[i].x1 >> L[i].y1 >> L[i].x2 >> L[i].y2;
    
 
    return 0;
}