직선 절단

Sawyer Steele은 금속 절단 공장을 운영한다. 고객이 필요한 조각의 설명을 보내면, Sawyer는 직사각형 금속판 위에 그 조각의 외곽선을 따라 그리고 직선 절단으로 조각을 잘라낸다. 그림 A.1의 왼쪽에 있는 현재 고객의 주문을 보자. Sawyer는 금속판 위에 삼각형을 그려 두었다. Sawyer는 기계를 설정해 이 조각을 세 번의 절단으로 잘라낼 수 있다. 다른 세 그림처럼 말이다. 먼저 점 A와 B를 지나는 직선을 따라, 다음으로 점 B와 C를 지나는 직선을 따라, 마지막으로 점 A와 C를 지나는 직선을 따라 자른다.

그림 A.1: 절단 예시.

Sawyer는 이 절단을 하려다가 이 세 번의 절단이 최선인지 궁금해졌다. 이 조각을 잘라내는 다른 방법도 있다. 예를 들어 점 A와 C를 지나는 직선을 먼저 따라 자르고, 그다음 점 C와 B를 지나는 직선을 따라, 마지막으로 점 A와 B를 지나는 직선을 따라 자를 수 있다. 이 조각을 잘라내는 각 방법마다 절단의 총 길이가 다르며, 길이가 짧을수록 기계의 마모가 적다.

최소 절단 길이를 구하는 일은 Sawyer의 능력 밖이라 그는 당신에게 도움을 청했다. 금속판 위 삼각형의 위치가 주어졌을 때, 그는 어떤 절단이 최소 총 절단 길이를 만드는지 알고 싶어 한다. 당신은 그런 프로그램을 작성할 코딩 능력이 있다고 생각하는가? 다시 말해, 잘라낼 배짱이 있는가?

입력은 여덟 개의 음이 아닌 정수 w h Ax Ay Bx By Cx Cy가 한 줄에 주어진다. w와 h(0 < w, h ≤ 1 000)는 직사각형 금속판의 너비와 높이이고(너비는 x축을 따라, 높이는 y축을 따라 간다), 나머지 여섯 값은 점 A, B, C의 x좌표와 y좌표이다(0 ≤ Ax, Bx, Cx ≤ w, 0 ≤ Ay, By, Cy ≤ h). 점은 직사각형 금속판의 모서리에 있을 수 있지만, 두 점이 같은 모서리에 있는 경우는 없다. 금속판의 왼쪽 아래 모서리는 (0, 0)에 있고 오른쪽 위 모서리는 (w, h)에 있다.

최적의 절단 집합에 대한 모든 절단의 총 길이를 소수점 둘째 자리에서 반올림해 출력한다. 다음 줄에는 p1-p2 p3-p4 p5-p6 형식으로 절단을 해야 하는 순서를 나타낸다. 여기서 각 pi는 A, B, C 중 하나이다. 첫 번째 쌍 p1-p2는 첫 번째 절단의 두 점을, 두 번째 쌍 p3-p4는 두 번째 절단의 두 점을, 세 번째 쌍은 세 번째 절단의 두 점을 나타낸다. 각 쌍은 항상 두 점을 알파벳 순서로 출력한다. 동점인 경우 A-B를 A-C와 B-C보다 우선하고, A-C를 B-C보다 우선하는 해를 출력한다.