문제 58
선분 교차 판정
평면 위의 두 선분 $AB$와 $CD$가 주어진다.
끝점에서 만나는 경우와 같은 직선 위에서 겹치는 경우도 만나는 것으로 본다.
$Q$개의 쿼리에 대해 두 선분이 만나는지 판정하라.
입력
첫 번째 줄에 정수 $Q$가 주어진다. $(1 \le Q \le 10^6)$
두 번째 줄부터 $Q$개의 줄에 걸쳐 두 선분의 끝점 좌표를 의미하는 여덟 정수 $x_1$, $y_1$, $x_2$, $y_2$, $x_3$, $y_3$, $x_4$, $y_4$가 공백으로 구분되어 주어진다. $(-10^9 \le x_i, y_i \le 10^9)$
각 점의 좌표는 $A=(x_1, y_1)$, $B=(x_2, y_2)$, $C=(x_3, y_3)$, $D=(x_4, y_4)$이다.
출력
각 쿼리마다 두 선분이 만나면 Yes를, 그렇지 않다면 No를 한 줄에 하나씩 출력한다.
예제 입력 1
6 0 0 4 4 0 4 4 0 0 0 1 1 2 2 3 3 0 0 4 0 2 0 6 0 0 0 2 0 2 0 2 2 0 0 1 0 2 0 3 0 -1 -1 1 1 2 0 3 0
예제 출력 1
Yes No Yes Yes No No
공식 해설
두 선분이 만나려면 각 선분의 끝점들이 다른 선분을 포함하는 직선의 서로 반대쪽에 있거나 직선 위에 있어야 한다. $\operatorname{ccw}$가 외적의 부호 $-1,0,1$을 반환하도록 두면 이 조건은
\[
\operatorname{ccw}(A,B,C)\operatorname{ccw}(A,B,D)\le0,
\]
\[
\operatorname{ccw}(C,D,A)\operatorname{ccw}(C,D,B)\le0
\]
이다. 등호를 포함하므로 끝점에서 만나는 경우도 허용한다.
다만 같은 직선 위에 있는 두 선분은 떨어져 있어도 위 조건을 만족한다. 이를 포함한 모든 경우를 한 번에 처리하려면 각 선분을 감싸는 축 정렬 직사각형도 겹치는지 확인한다. 즉 $x$좌표 구간과 $y$좌표 구간이 각각 겹쳐야 한다.
두 부호 조건과 두 좌표 구간의 겹침 조건이 모두 참이면 교차한다. 일직선에서는 좌표 구간의 겹침이 실제 선분의 겹침과 같고, 일직선이 아니면 서로의 직선을 가로지르는 조건이 교점을 보장한다. 길이가 $0$인 선분도 같은 조건으로 판정할 수 있다.
경계에 닿는 경우도 정확히 구분하도록 외적은 정수로 계산한다. 두 외적 자체의 곱은 필요하지 않으며, 각각의 부호만 비교하면 된다. 시간복잡도는 $O(Q)$, 추가 공간복잡도는 $O(1)$이다.
구현 · 언어별 풀이
C++ 구현
좌표와 외적을 long long으로 계산하고 외적의 부호를 반환하는 함수를 둔다. 교차 조건에서는 외적값 자체가 아니라 $-1$, $0$, $1$인 부호들만 곱한다. 좌표 구간의 겹침에는 min, max를 사용하고 등호를 포함한다.
C 구현
외적 부호들을 비교하되 두 외적을 곱해서 검사하지 않는다. 각각 long long에 들어가도 곱은 넘을 수 있다. 일직선이면 min/max로 두 축의 닫힌 구간 겹침을 검사한다.
Python 구현
외적과 좌표 비교는 Python int로 처리한다. 일직선인 경우 x,y 양쪽의 닫힌 구간이 겹치는지 검사한다. 끝점이 닿는 경우와 길이 0인 선분도 포함한다.
Java 구현
CCW 결과의 부호를 -1,0,1로 만든 뒤 비교한다. 원래 외적끼리 곱하지 않는다. 모든 좌표와 외적은 long이며 일직선에서는 양 축 bounding box를 확인한다.
Rust 구현
ccw는 i64로 계산하고 signum()으로 부호를 얻는다. 두 큰 외적을 곱하지 않고 부호끼리 비교한다. 일직선에서는 min/max의 닫힌 구간 비교로 접촉도 포함한다.
JavaScript 구현
각 외적은 좌표 차를 BigInt로 바꾼 뒤 곱해 계산한다. 외적 값 전체를 서로 곱할 필요는 없다. 외적을 $-1$, $0$, $1$ 중 하나인 Number 부호로 반환하면 두 부호의 곱이 $0$ 이하인지 작은 정수로 비교할 수 있다.
네 점이 한 직선 위에 있을 때에는 $x$와 $y$ 양쪽 축에서 구간이 겹치는지 확인한다. 좌표 자체와 Math.min·Math.max 비교는 안전한 Number 범위이다. 끝점 접촉, 수직 선분, 길이 $0$인 선분도 겹침 검사에서 그대로 처리한다.
질의마다 여덟 좌표를 읽고 즉시 결과를 만든다. 최대 백만 질의에서 모든 점 객체와 모든 출력 문자열을 계속 모으지 말고, Buffer 파싱·일정 크기의 묶음 출력을 사용한다. 정확한 정수 비교를 사용하므로 epsilon을 넣지 않는다.