아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

사슬 고리

시간 제한3초메모리 제한128 MB

요약
3차원 공간에 놓인 두 단위원이 사슬 고리처럼 엮였는지 중심과 방향 벡터로 판정합니다.
난이도

보통10점 중 7점

유형
기하, 수학
정답자
아직 제출이 없습니다

문제

3차원 공간에 반지름이 1인 원이 두 개 있다. ii번째 원은 중심 ci=(cxi,cyi,czi)c_i = (cx_i, cy_i, cz_i)와 서로 직교하는 두 단위벡터 uiu_i, viv_i로 정해지고, 원 위의 점은 다음 집합이다.

{ ci+uicos⁡t+visin⁡t  :  0≤t<2π }\{\, c_i + u_i \cos t + v_i \sin t \;:\; 0 \le t < 2\pi \,\}

두 원이 사슬의 고리처럼 얽혀 있는지 판정하라. 한 원을 다른 원에 통과시키지 않고는 아무리 움직여도 떼어놓을 수 없을 때 얽혀 있다고 한다.

입력

첫째 줄에 실수 세 개 cx1cx_1, cy1cy_1, cz1cz_1이 주어진다. 첫 번째 원의 중심 좌표이며 −3≤cx1,cy1,cz1≤3-3 \le cx_1, cy_1, cz_1 \le 3이다.

둘째 줄에 실수 여섯 개 vx1,1vx_{1,1}, vy1,1vy_{1,1}, vz1,1vz_{1,1}, vx1,2vx_{1,2}, vy1,2vy_{1,2}, vz1,2vz_{1,2}가 주어진다. 각 값은 −1-1 이상 11 이하이다. 앞의 세 개는 중심에서 원주를 향하는 단위벡터 u1u_1이고, 뒤의 세 개는 같은 방식으로 정해지는 단위벡터 v1v_1이다. 두 벡터는 서로 직교한다.

셋째 줄과 넷째 줄에 두 번째 원의 정보가 같은 형식으로 주어진다.

두 원이 서로 닿는 입력은 주어지지 않는다.

출력

두 원이 사슬의 고리처럼 얽혀 있으면 "YES"를, 그렇지 않으면 "NO"를 출력한다. 따옴표는 출력하지 않는다.

예제4

  1. 예제 1

    입력
    0.0 0.0 0.0
    1.0 0.0 0.0 0.0 1.0 0.0
    1.0 0.0 0.5
    1.0 0.0 0.0 0.0 0.0 1.0
    
    예상 출력
    YES
    
  2. 예제 2

    입력
    0.0 0.0 0.0
    1.0 0.0 0.0 0.0 1.0 0.0
    0.0 3.0 0.0
    0.0 1.0 0.0 -1.0 0.0 0.0
    
    예상 출력
    NO
    
  3. 예제 3

    입력
    1.2 2.3 -0.5
    1.0 0.0 0.0 0.0 1.0 0.0
    1.1 2.3 -0.4
    1.0 0.0 0.0 0.0 0.70710678 0.70710678
    
    예상 출력
    YES
    
  4. 예제 4

    입력
    1.2 2.3 -0.5
    1.0 0.0 0.0 0.0 1.0 0.0
    1.1 2.7 -0.1
    1.0 0.0 0.0 0.0 0.70710678 0.70710678
    
    예상 출력
    NO