연결된 삼각형
시간 제한2초메모리 제한1024 MB
3차원 공간의 점 여섯 개가 주어질 때, 두 삼각형으로 나눈 방법 중 서로 연결된 경우를 모두 찾습니다.
연결된 삼각형
삼각형 △ABC는 다음 조건 중 하나를 만족하면 삼각형 △DEF에 의해 연결되어 있다고 한다.
- △DEF의 변 중 정확히 하나가 △ABC의 내부를 지난다(△ABC와 같은 평면 위에서 본다, 아래 그림 참고). 또는
- △DEF의 꼭짓점 하나가 △ABC의 내부에 있고, 그 꼭짓점에 인접한 두 변이 △ABC가 놓인 평면의 서로 다른 쪽에 있다.
△ABC가 △DEF에 의해 연결되어 있으면, △DEF도 △ABC에 의해 연결되어 있다. 이때 두 삼각형은 서로 연결되어 있다고 한다.
3차원 공간의 점들이 일반 위치에 있다는 것은 어떤 네 점도 같은 평면에 있지 않다는 뜻이다(세 점이 같은 직선 위에 있지 않다는 뜻이기도 하다).
일반 위치에 있는 3차원 공간의 임의의 여섯 점은, 세 점씩 두 묶음으로 나누었을 때 각 묶음이 만드는 두 삼각형이 서로 연결되도록 나누는 방법이 적어도 하나 있다. 점들이 일반 위치에 있으면 네 점이 △ABC의 평면 위에 놓일 수 없으므로 위 2번 조건은 일어나지 않는다.
입력
입력은 여섯 줄이다. 각 줄에는 한 점의 좌표 x, y, z가 공백으로 구분된 배정밀도 실수로 주어진다. 점은 모두 여섯 개다.
출력
첫 줄에는 찾은 연결된 삼각형 쌍의 개수 N을 10진 정수로 출력한다.
N은 그다음 N개의 줄로 이어진다. 각 줄에는 공백으로 구분된 10진 정수 m과 n을 출력한다. 이는 점 1, m, n을 한 삼각형으로, 나머지 점을 다른 삼각형으로 잡았을 때 연결된 쌍이 된다는 뜻이다. 각 줄에서 m < n이며, 줄은 사전순으로 정렬한다. 즉 m1 n1 줄이 m2 n2 줄보다 위에 있다면, m1 < m2이거나 m1 = m2이고 n1 < n2이다.