8065 : 방향 판정
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
2차원 평면 위에 세 점 $A(x_1, y_1)$, $B(x_2, y_2)$, $C(x_3, y_3)$가 순서대로 주어집니다.
이 세 점이 이루는 방향이 반시계 방향(CCW)인지, 시계 방향(CW)인지, 아니면 일직선 상에 위치해 있는지 판별하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le Q \le 30{,}000$
• 모든 좌표값의 절댓값 $\le 10^9$
이 세 점이 이루는 방향이 반시계 방향(CCW)인지, 시계 방향(CW)인지, 아니면 일직선 상에 위치해 있는지 판별하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le Q \le 30{,}000$
• 모든 좌표값의 절댓값 $\le 10^9$
입력 설명
첫째 줄에 방향 판정을 수행할 쿼리의 개수 $Q$가 주어집니다. ($1 \le Q \le 30{,}000$)
둘째 줄부터 $Q$개의 줄에 걸쳐 각 줄에 세 점의 좌표를 나타내는 6개의 정수 $x_1, y_1, x_2, y_2, x_3, y_3$가 공백으로 구분되어 주어집니다.
모든 좌표값의 절댓값은 $10^9$ 이하입니다.
둘째 줄부터 $Q$개의 줄에 걸쳐 각 줄에 세 점의 좌표를 나타내는 6개의 정수 $x_1, y_1, x_2, y_2, x_3, y_3$가 공백으로 구분되어 주어집니다.
모든 좌표값의 절댓값은 $10^9$ 이하입니다.
출력 설명
입력된 각 쿼리에 대하여 방향을 판정한 결과를 한 줄에 하나씩 출력합니다.
- 세 점이 반시계 방향을 이루면
- 세 점이 시계 방향을 이루면
- 세 점이 일직선 상에 놓여 있으면
- 세 점이 반시계 방향을 이루면
1을 출력합니다.- 세 점이 시계 방향을 이루면
-1을 출력합니다.- 세 점이 일직선 상에 놓여 있으면
0을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4
0 0 1 1 2 2
0 0 1 0 0 1
0 0 0 1 1 0
0 0 10 10 5 5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
0
1
-1
0도움
세 점의 외적(Cross Product) 연산을 구현하여 양수, 음수, 0 여부를 조사합니다.
연산 과정에서 $10^9$ 단위 좌표값 곱셈에 의한 정수 범위 오버플로우가 나지 않도록 64비트 정수형을 사용하여 연산해야 합니다.
연산 과정에서 $10^9$ 단위 좌표값 곱셈에 의한 정수 범위 오버플로우가 나지 않도록 64비트 정수형을 사용하여 연산해야 합니다.