5036 : 선분의 교차 판정
문제 설명
2차원 평면 위에 2개의 선분이 있습니다.
\n첫 번째 선분은 좌표 $(x_1, y_1)$과 좌표 $(x_2, y_2)$를 잇고,
\n두 번째 선분은 좌표 $(x_3, y_3)$과 좌표 $(x_4, y_4)$를 잇습니다.
이 2개의 선분이 교차한다면 Yes를, 교차하지 않는다면 No를 출력하십시오.
여기서 2개의 선분이 교차한다는 것은, 두 선분에 공통으로 포함되는 점이 적어도 하나 존재하는 것을 의미합니다.
\n\n[제약 조건]\n
- \n
- $-10^9 \\le x_1, x_2, x_3, x_4, y_1, y_2, y_3, y_4 \\le 10^9$ \n
- $(x_1, y_1)$과 $(x_2, y_2)$는 서로 다른 점입니다. \n
- $(x_3, y_3)$과 $(x_4, y_4)$는 서로 다른 점입니다. \n
- 입력되는 모든 값은 정수입니다. \n
\n
\n\n
🔎 알고리즘 힌트 — 외적(Cross Product)과 CCW로 선분 교차 판정하기
\n\n \n1. 벡터의 외적과 2차원 방향 판별
\n\n 두 3차원 벡터의 외적(Cross Product, $\\vec{A} \\times \\vec{B}$)은 두 벡터가 이루는 평면에 수직인 새로운 벡터입니다.
• 오른손 법칙 (방향): 오른손 네 손가락을 $\\vec{A}$에서 $\\vec{B}$ 방향으로 감아쥘 때, 엄지손가락이 가리키는 방향이 외적 벡터의 방향입니다.
• 2차원 평면($z=0$)에서의 해석: 2차원 평면의 두 벡터를 3차원으로 확장하면 외적 벡터는 오직 $z$축 성분만 갖습니다.
$$\\vec{A} \\times \\vec{B} = \\big(0,\\; 0,\\; a_x b_y - a_y b_x\\big)$$
• $z$ 성분의 부호: $a_x b_y - a_y b_x > 0$이면 엄지가 화면 앞(+z)을 향하는 반시계 방향(CCW), $< 0$이면 화면 안(-z)으로 들어가는 시계 방향(CW)입니다.
• 기하학적 크기: 절댓값 $|a_x b_y - a_y b_x|$는 두 벡터가 이루는 평행사변형의 넓이와 같습니다.\n
2. CCW 함수 — 세 점의 방향 판별
\n\n 세 점 $P_1, P_2, P_3$가 주어졌을 때, $P_1 \\to P_2 \\to P_3$ 방향의 꺾임을 외적으로 판별합니다.
\n 기준 벡터: $\\overrightarrow{P_1P_2}$와 $\\overrightarrow{P_1P_3}$의 외적 = $(x_2-x_1)(y_3-y_1)-(y_2-y_1)(x_3-x_1)$\n
3. CCW로 선분 교차 판정하기
\n\n 선분 $P_1P_2$와 선분 $P_3P_4$가 교차하려면 두 조건을 모두 만족해야 합니다.
\n • $P_3$과 $P_4$가 직선 $P_1P_2$를 기준으로 서로 반대편
\n • $P_1$과 $P_2$가 직선 $P_3P_4$를 기준으로 서로 반대편\n
4. 일직선(Collinear) 엣지 케이스 처리
\n\n CCW 값이 모두 0이면 세 점이 같은 직선 위에 있습니다. 이때는 단순 곱 조건으로는 부족하고,
\n bounding box 겹침을 추가로 확인해야 합니다.\n
\n 1. $d_1 = \\text{CCW}(P_1,P_2,P_3) \\times \\text{CCW}(P_1,P_2,P_4)$, $d_2 = \\text{CCW}(P_3,P_4,P_1) \\times \\text{CCW}(P_3,P_4,P_2)$ 계산
\n 2. $d_1 = 0$ 이고 $d_2 = 0$ ⇒ 일직선 케이스: bounding box 겹침으로 판정
\n 3. $d_1 \\le 0$ 이고 $d_2 \\le 0$ ⇒ Yes (교차)
\n 4. 그 외 ⇒ No (비교차)\n
입력 설명
입력은 다음과 같이 4개의 줄에 걸쳐 주어집니다.
$x_2$ $y_2$
$x_3$ $y_3$
$x_4$ $y_4$
출력 설명
두 선분이 교차한다면 Yes를, 교차하지 않는다면 No를 출력하십시오.
입력 예시
COPY
복사되었습니다!
0 0
3 3
0 3
3 0
출력 예시
COPY
복사되었습니다!
Yes