문제 57

세 점의 방향

내 상태: 미제출
난이도: 57번 문제 난이도 보기

Gold V
출제자: rlatjwls7882
시간 제한: 1000 ms
메모리 제한: 512 MB

태그 보기

기하학

평면 위의 세 점 $A$, $B$, $C$가 주어진다.

점 $A$에서 점 $B$로 이동한 뒤 점 $C$로 이동할 때의 방향을 판정하라.

$Q$개의 쿼리에 대해 각각의 방향을 출력하라.

입력

첫 번째 줄에 정수 $Q$가 주어진다. $(1 \le Q \le 10^6)$

두 번째 줄부터 $Q$개의 줄에 걸쳐 세 점의 좌표를 의미하는 여섯 정수 $x_1$, $y_1$, $x_2$, $y_2$, $x_3$, $y_3$이 공백으로 구분되어 주어진다. $(-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)$이다.

출력

각 쿼리마다 반시계 방향이면 1, 시계 방향이면 -1, 일직선이면 0을 한 줄에 하나씩 출력한다.

예제 입력 1

5
0 0 1 0 1 1
0 0 1 0 1 -1
0 0 1 1 2 2
1 1 3 4 5 2
-1 -1 -2 -3 4 5

예제 출력 1

공식 해설 풀이 스포일러 보기 접기

$A$를 기준으로 두 벡터 $B-A$, $C-A$의 외적을 계산한다.
\[ z=(x_2-x_1)(y_3-y_1)-(y_2-y_1)(x_3-x_1). \]

$z>0$이면 $C$가 $A\to B$ 방향의 왼쪽에 있으므로 반시계 방향이다. $z<0$이면 오른쪽이므로 시계 방향이고, $z=0$이면 세 점이 일직선이다. 따라서 부호에 따라 $1$, $-1$, $0$을 출력한다.

일직선 여부를 정확히 구분하려면 외적을 정수로 계산해야 한다. 좌표 차의 절댓값은 최대 $2\cdot10^9$이므로 각 곱과 그 차를 정확히 표현할 수 있는 범위를 고려한다.

질의당 상수 번 계산하므로 시간복잡도는 $O(Q)$, 추가 공간복잡도는 $O(1)$이다.

구현 · 언어별 풀이

C++ 구현

좌표를 long long으로 읽으면 차와 곱도 같은 자료형으로 계산된다. 주어진 범위에서 외적의 절댓값은 $8\cdot10^{18}$ 이하이다. int 좌표를 사용한다면 차의 곱을 계산하기 전에 형을 넓혀야 한다. 최종 외적의 부호만 $1$, $0$, $-1$로 출력한다.

C 구현

좌표를 long long으로 읽어 차와 외적을 계산한다. 좌표 차는 최대 $2 \cdot 10^{9}$, 외적 절댓값은 최대 $8 \cdot 10^{18}$이라 long long 안이다. 실수 기울기를 비교하지 않는다.

Python 구현

Python int로 좌표 차와 외적을 계산하고 부호만 출력한다. 나눗셈이나 atan2가 필요 없으므로 수직선·일직선에서도 같은 식을 사용할 수 있다.

Java 구현

좌표는 long으로 변환한 뒤 빼고 곱한다. (x2-x1)*(y3-y1)-(y2-y1)*(x3-x1)의 부호를 비교하면 된다. int 곱을 계산한 뒤 long에 저장하면 늦다.

Rust 구현

좌표·차·외적에 i64를 사용한다. 범위상 외적은 i64에 들어가며 i128은 필수는 아니다. 양수·0·음수를 직접 비교한다.

JavaScript 구현

좌표 자체는 Number로 정확하게 읽을 수 있지만 외적의 중간 곱은 안전 정수 범위를 넘는다. 좌표 차를 구한 뒤 곱하기 전에 BigInt로 바꾸면 정수 부호를 정확하게 판단할 수 있다.

function ccw(ax, ay, bx, by, cx, cy) {
    const cross = BigInt(bx - ax) * BigInt(cy - ay)
                - BigInt(by - ay) * BigInt(cx - ax);
    return cross > 0n ? 1 : cross < 0n ? -1 : 0;
}

좌표 차의 절댓값은 $2\cdot10^9$ 이하라 변환 전 뺄셈도 정확하다. 곱을 Number로 먼저 계산하고 그 결과를 BigInt로 바꾸는 것은 이미 잃은 정밀도를 복구하지 못한다.

최대 백만 질의의 좌표를 배열로 전부 저장하지 말고, 여섯 좌표씩 읽어 부호만 출력한다. Buffer 숫자 파싱과 묶음 출력으로 입력·출력의 임시 메모리를 제한할 수 있다.

제출

언어