삼각형 변환

아직 제출이 없습니다시간 제한5초메모리 제한512 MB

문제

현우는 삼각형 그림을 두 장 갖고 있다. 두 장을 책상 위에 겹쳐 놓으면 두 번째 그림이 첫 번째 그림 안에 완전히 들어간다. 경계에 닿아도 된다. 두 그림의 꼭짓점은 주어진 순서대로 짝을 이룬다. 첫 번째 그림의 첫 번째 꼭짓점은 두 번째 그림의 첫 번째 꼭짓점에 대응하고, 두 번째와 세 번째 꼭짓점도 마찬가지다.

현우는 두 번째 그림이 첫 번째 그림을 회전하고 축소해서 옮겨 놓은 것이라고 생각한다. 즉 다음 세 동작을 이 순서로 적용하는 변환 TT가 있고, 모든 kk에 대해 TT가 첫 번째 그림의 kk번째 꼭짓점을 두 번째 그림의 kk번째 꼭짓점으로 보낸다고 생각한다.

  • 원점을 중심으로 어떤 각도만큼 회전한다.
  • 원점을 기준으로 배율 ss만큼 축소한다. ss0<s<10 < s < 1을 만족한다.
  • 평행이동한다.

뒤집기는 쓸 수 없다. 이런 TT가 있으면 TT가 자리를 바꾸지 않는 점, 즉 두 그림에서 좌표가 같은 지점이 정확히 하나 있다. 그 점의 좌표를 구하라. 이런 TT가 없으면, 예를 들어 두 번째 그림이 첫 번째 그림의 거울상이면 No Solution을 출력한다.

입력

첫 줄에 테스트케이스의 개수 NN이 주어진다. 1N101 \le N \le 10이다.

각 테스트케이스는 두 줄이다. 첫 줄에는 첫 번째 그림의 꼭짓점, 둘째 줄에는 두 번째 그림의 꼭짓점이 x1 y1 x2 y2 x3 y3 형태로 주어지며, 수 사이는 공백 하나로 구분한다. 모든 좌표는 10000-10000 이상 1000010000 이하의 정수다.

각 삼각형의 세 꼭짓점은 한 직선 위에 있지 않다. 삼각형의 모양에는 그 밖의 제한이 없다.

두 번째 삼각형은 첫 번째 삼각형 안에 있고, 넓이는 첫 번째 삼각형의 넓이보다 작다.

답이 있는 테스트케이스에서는 답의 두 좌표를 소수점 아래 여섯째 자리로 반올림할 때 올릴지 내릴지가 애매해지는 경우가 없다.

출력

각 테스트케이스마다 한 줄씩 출력한다. 줄의 앞부분은 Case #, 테스트케이스 번호, : 를 이 순서로 이어 붙인 문자열이다. 번호는 1부터 센다.

변환 TT가 있으면 그 뒤에 겹치는 점의 xx좌표와 yy좌표를 소수점 아래 여섯째 자리까지 반올림해서 공백 하나로 구분해 출력한다. 반올림한 값이 00인 좌표는 부호를 붙이지 않고 0.000000으로 출력한다.

변환 TT가 없으면 그 뒤에 No Solution을 출력한다.