[17386] 선분 교차 1

문제 링크 : https://www.acmicpc.net/problem/17386

17386 - 선분 교차 1

본문

2차원 좌표 평면 위의 두 선분 $L_1, L_2$가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자.

$L_1$의 양 끝 점은 ($x_1, y_1$), ($x_2, y_2$), $L_2$의 양 끝 점은 ($x_3, y_3$), ($x_4, y_4$)이다.

입력

첫째 줄에 $L_1$의 양 끝 점 $x_1, y_1, x_2, y_2$가, 둘째 줄에 $L_2$의 양 끝 점 $x_3, y_3, x_4, y_4$가 주어진다. 세 점이 일직선 위에 있는 경우는 없다.

출력

$L_1$과 $L_2$가 교차하면 1, 아니면 0을 출력한다.

제한

시간 제한	메모리 제한
0.25sec	512MB

• $-1000000 \leq x_1, y_1, x_2, y_2, x_3, y_3, x_4, y_4 \leq 1000000$
• $x_1, y_1, x_2, y_2, x_3, y_3, x_4, y_4$는 정수
• 선분의 길이는 $0$보다 크다.

---

풀이

우선 선분 2개가 교차하는 case를 생각해보자. 그림으로 그려보면 아래가 하나의 예시가 될 것이다.

선분 AB에 대해서 먼저 생각해보자. C는 AB의 왼쪽, D는 CD의 오른쪽에 존재한다. ABC를 생각하면 반시계 방향, ABD를 생각하면 시계방향으로 관계를 가지는 것을 알 수 있다.

우리는 여기서 CCW를 생각해볼 수 있다. CCW는 참고 알고리즘을 참고하자. 우리는 CCW 알고리즘을 이용하여 3개의 점의 방향관계를 알 수 있다. AB를 기준으로 잡고, 우리는 ABC의 관계와 ABD의 관계를 계산할 수 있다. 선분이 교차하기 위해서는 둘 중 하나는 시계방향 (양수), 다른 하나는 반시계방향 (음수) 관계를 가져야함을 알 수 있다. 그렇다면, 2개의 값을 곱하면 두 선분이 교차하는지 계산할 수 있다. 그 값이 음수면 되는 것이다.

문제는, AB선분을 기준으로 잡았다는 것이다. 우리는 사실 CD 선분도 기준으로 잡을 수 있다. 그리고, CDA와 CDB도 서로 다른 방향관계를 보인다고 계산할 수 있다. 그러므로, 우리는 CDA와 CDB의 CCW 또한 계산해주어야한다.

값을 모두 계산하였다면 합치면 된다. 합치는 식은 아래와 같다. 모두 음수가 나와야함에 유의하자.

\[\begin{cases} \text{true} & \text{if } \text{ccw}(A, B, C) \times \text{ccw}(A, B, D) < 0 \text{ and }\\ & \text{ccw}(C, D, A) \times \text{ccw}(C, D, B) < 0\\ \text{false} & \text{otherwise} \end{cases}\]

위 식만 적용하면 문제를 해결할 수 있다.

• 참고 알고리즘 : CCW

코드

사용 언어 : C

최종 수정일 : 2023 / 2 / 28

#include <stdio.h>

typedef long long ll;
typedef struct Node {
    ll x, y;
} ND;

ll ccw(ND a, ND b, ND c) {
    ll t1 = (a.x * b.y + b.x * c.y + c.x * a.y);
    ll t2 = (b.x * a.y + c.x * b.y + a.x * c.y);

    if (t1 - t2 > 0) {
        return 1;
    } else if (t1 - t2 < 0) {
        return -1;
    } else {
        return 0;
    }
}

int main() {
    ll x1, y1, x2, y2;
    ll x3, y3, x4, y4;
    scanf("%lld %lld %lld %lld", &x1, &y1, &x2, &y2);
    scanf("%lld %lld %lld %lld", &x3, &y3, &x4, &y4);

    ND a = (ND){x1, y1}, b = (ND){x2, y2}, c = (ND){x3, y3}, d = (ND){x4, y4};

    printf("%d", ((ccw(a, b, c) * ccw(a, b, d) < 0) && (ccw(c, d, a) * ccw(c, d, b) < 0)));
    return 0;
}