8066 : 선분 교차 판정
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
2차원 평면 위에 두 선분 $AB$와 $CD$가 주어질 때, 두 선분이 서로 만나는지(교차하는지) 여부를 판별하는 프로그램을 작성하십시오.
선분의 끝점이 다른 선분 위에 놓이거나 서로 한 점에서 만나는 경우도 교차하는 것으로 간주합니다.
[제약 조건]
• $1 \le Q \le 10{,}000$
• 모든 좌표값의 절댓값 $\le 10^9$
선분의 끝점이 다른 선분 위에 놓이거나 서로 한 점에서 만나는 경우도 교차하는 것으로 간주합니다.
[제약 조건]
• $1 \le Q \le 10{,}000$
• 모든 좌표값의 절댓값 $\le 10^9$
입력 설명
첫째 줄에 선분 교차 판정을 수행할 쿼리의 개수 $Q$가 주어집니다. ($1 \le Q \le 10{,}000$)
둘째 줄부터 $Q$개의 줄에 걸쳐 각 줄에 두 선분의 양 끝점 좌표를 나타내는 8개의 정수 $x_A, y_A, x_B, y_B, x_C, y_C, x_D, y_D$가 공백으로 구분되어 주어집니다.
모든 좌표값의 절댓값은 $10^9$ 이하입니다.
둘째 줄부터 $Q$개의 줄에 걸쳐 각 줄에 두 선분의 양 끝점 좌표를 나타내는 8개의 정수 $x_A, y_A, x_B, y_B, x_C, y_C, x_D, y_D$가 공백으로 구분되어 주어집니다.
모든 좌표값의 절댓값은 $10^9$ 이하입니다.
출력 설명
입력된 각 쿼리에 대하여 두 선분이 만나면
1, 만나지 않으면 0을 한 줄에 하나씩 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4
1 1 5 5 1 5 5 1
1 1 5 5 6 6 9 9
1 1 5 5 5 5 7 7
1 1 5 5 3 3 7 7
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1
0
1
1도움
세 점의 방향 판정(CCW) 함수를 네 번 호출하여 관계를 분석합니다.
네 점이 모두 일직선 상에 있는 특수한 경우에는 두 선분의 좌표 범위가 서로 겹치는지 체크하는 경계 조건 처리가 필요합니다.
네 점이 모두 일직선 상에 있는 특수한 경우에는 두 선분의 좌표 범위가 서로 겹치는지 체크하는 경계 조건 처리가 필요합니다.