레이저 교차 판정
골드 II의견: 0
두 개의 레이저 선분 \(\overline{P_1 P_2}\) 와 \(\overline{P_3 P_4}\) 가 주어질 때, 두 선분이 교차하는지 판정합니다.
다음 경우 모두 "교차한다"로 봅니다:
- 두 선분이 한 점에서 가로질러 만나는 경우
- 한 선분의 끝점이 다른 선분 위(끝점 포함)에 닿는 경우 (끝점 접촉)
- 두 선분이 같은 직선 위에 있으면서 일부 구간 또는 한 점을 공유하는 경우 (공선 겹침)
그 외(전혀 만나지 않음)는 "교차하지 않는다"입니다. 선분의 길이가 \(0\) (두 끝점이 같은 점)일 수도 있으며, 이 경우 그 점이 상대 선분 위에 있으면 교차로 봅니다.
좌표가 크므로 CCW를 정수 연산으로 계산해야 합니다. 총 \(Q\) 개의 질의가 주어집니다.
- \(1 \le Q \le 22\,000\)
- \(-10^9 \le\) 모든 좌표 \(\le 10^9\)
첫 줄에 질의 수 \(Q\) 가 주어집니다.
이어서 \(Q\) 개의 줄에 각 질의가 \(x_1\ y_1\ x_2\ y_2\ x_3\ y_3\ x_4\ y_4\) 형태로 주어집니다. \((x_1,y_1)\)–\((x_2,y_2)\) 가 첫 선분, \((x_3,y_3)\)–\((x_4,y_4)\) 가 둘째 선분입니다.
각 질의에 대해 교차하면 \(1\), 아니면 \(0\) 을 한 줄에 하나씩 출력합니다.
3
0 0 4 4 0 4 4 0
0 0 2 2 3 3 5 5
0 0 1 1 2 2 3 31
0
0첫 질의는 두 선분이 가운데서 교차하므로 \(1\). 둘째는 한 직선 위에서 겹치지 않고 떨어져 있으므로 \(0\). 셋째는 같은 직선 위에서 점 \((2,2)\) 를 공유하며 닿으므로 \(1\) 입니다.
2
0 0 5 0 5 0 5 5
0 0 2 0 3 0 5 01
0첫 질의는 끝점 \((5,0)\) 을 공유하므로(끝점 접촉도 교차로 봄) \(1\). 둘째는 같은 직선 위에서 \([3,5]\) 구간이 겹치므로 \(1\) 입니다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
레이저 교차 판정
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
레이저 교차 판정