세 점의 방향 판정
골드 II의견: 0
평면 위의 세 점 \(A, B, C\) 가 주어질 때, 점 \(A \to B \to C\) 로 이동하는 방향이 어떻게 꺾이는지를 판정합니다.
- 반시계 방향(좌회전)이면 \(1\)
- 시계 방향(우회전)이면 \(-1\)
- 세 점이 한 직선 위에 있으면 \(0\)
을 출력합니다. 이는 외적의 부호로 판정할 수 있습니다: \(\mathrm{CCW} = \mathrm{sgn}\big((B_x-A_x)(C_y-A_y)-(B_y-A_y)(C_x-A_x)\big)\).
좌표가 매우 크므로 반드시 정수 연산으로 정확히 계산해야 합니다 (실수 오차 주의).
총 \(Q\) 개의 질의가 주어집니다.
- \(1 \le Q \le 30\,000\)
- \(-10^9 \le\) 모든 좌표 \(\le 10^9\)
- 점들이 서로 같을 수 있습니다.
첫 줄에 질의 수 \(Q\) 가 주어집니다.
이어서 \(Q\) 개의 줄에 각 질의가 \(A_x\ A_y\ B_x\ B_y\ C_x\ C_y\) 형태로 주어집니다.
각 질의에 대해 \(1\), \(-1\), \(0\) 중 하나를 한 줄에 하나씩 출력합니다.
3
0 0 1 0 0 1
0 0 1 0 1 0
0 0 2 2 1 11
0
0첫 질의는 반시계(좌회전)이므로 \(1\), 둘째는 시계(우회전)이므로 \(-1\), 셋째는 세 점이 일직선 위에 있으므로 \(0\) 입니다.
2
0 0 4 0 2 -3
0 0 1000000000 1000000000 -1000000000 -1000000000-1
0첫 질의는 시계 방향이라 \(-1\), 둘째는 세 점이 직선 \(y=x\) 위에 있어 \(0\) 입니다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
세 점의 방향 판정
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
세 점의 방향 판정