돛 조각 맞추기 - 9

이틀 동안 이어진 폭풍우 끝에 선원 무리가 지중해의 한 사막 섬에 난파했다. 무전기가 고장 나서 도움을 요청할 수 없다. 살아남을 길은 뗏목을 타고 탈출하는 것뿐이고, 뗏목에는 돛이 필요하다.

그들은 난파선에서 주돛을 건졌지만, 돛은 여러 조각으로 찢어져 있었다. 원래 돛을 복원하려면 조각들을 꿰매야 한다.

각 조각은 삼각형이다. 돛에는 줄무늬가 있어서 각 삼각형의 올바른 방향을 쉽게 알 수 있다. 조각은 방향을 지켜야 한다. 그렇지 않으면 돛이 바람을 제대로 견디지 못하고 다시 찢어질 수 있다. 선원들은 몇 시간 동안 원래 배열을 찾았지만 실패했다. 그래서 그 배열을 찾는 프로그램을 만들어 달라고 당신에게 부탁했다.

각 삼각형은 꼭짓점의 평면 좌표로 주어진다. 원래 돛은 정수 너비 $X$와 높이 $Y$를 가진 직사각형이다. 조각을 회전하지 않고 옮겨서 돛을 복원하라. 구체적으로 다음 조건을 만족해야 한다.

• 직사각형 전체를 덮어야 한다.
• 두 삼각형이 겹치면 안 된다. 즉 서로 다른 두 삼각형의 내부에 동시에 속하는 점이 없어야 한다.
• 어떤 삼각형의 일부도 직사각형 밖으로 나가면 안 된다.

모든 입력에 대해 해가 존재한다고 가정해도 된다. 조각 넓이의 합은 돛의 넓이와 같다. 같은 모양의 조각이 여러 개 있을 수 있다.

첫 줄에 공백으로 구분된 정수 $N$, $X$, $Y$가 주어진다. $X$는 돛의 너비, $Y$는 높이이며 $1 \le X, Y \le 1\,000\,000$이다. $N$은 삼각형 조각의 개수이며 $2 \le N \le 1\,000$이다.

$i+1$번째 줄에는 공백으로 구분된 정수 여섯 개 $A_{i,x}$, $A_{i,y}$, $B_{i,x}$, $B_{i,y}$, $C_{i,x}$, $C_{i,y}$가 주어진다. 이는 $i$번째 삼각형의 세 꼭짓점 $A_i$, $B_i$, $C_i$를 나타낸다. 모든 좌표는 $0 \le \text{좌표} \le 1\,000\,000$을 만족한다.

입력에서 삼각형의 위치는 중요하지 않다. 예를 들어 예시 입력의 세 번째 줄을 6 6 14 5 16 6으로 바꾸어도 조각의 집합은 같다.

$N$줄을 출력한다. $i$번째 줄에는 공백으로 구분된 정수 두 개 $A^*_{i,x}$와 $A^*_{i,y}$를 출력한다. 이는 $i$번째 조각을 제자리로 옮긴 뒤 점 $A_i$의 좌표다. 그림과 같이 돛의 왼쪽 아래 모서리는 항상 $(0, 0)$이고, 오른쪽 위 모서리는 $(X, Y)$이다.