Bạn được cho hai bức hình hình tam giác. Bức hình thứ hai là một phiên bản đã được dịch chuyển, xoay và thay đổi tỉ lệ của bức hình thứ nhất. Hai tam giác này được đặt trên bàn, với tam giác thứ hai nằm hoàn toàn bên trong (có thể chạm vào biên của) tam giác thứ nhất. Tam giác thứ hai luôn được thu nhỏ theo một tỉ lệ \(S\) nằm trong khoảng \(0 < S < 1\).

Bạn cần xử lý hình ảnh và tìm một điểm trong bức hình trùng với chính điểm đó trong phiên bản thu nhỏ. Nếu có nhiều hơn một giải pháp, bạn có thể trả về bất kỳ điểm nào. Nếu không có giải pháp, hãy in "No Solution" cho trường hợp đó.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(N\). Sau đó, với mỗi bộ test, sẽ có hai dòng, mỗi dòng chứa sáu số nguyên cách nhau bởi dấu cách -- tọa độ của một trong các tam giác -- theo định dạng "\(x_1\) \(y_1\) \(x_2\) \(y_2\) \(x_3\) \(y_3\)". Điểm \((x_1, y_1)\) trong tam giác thứ nhất tương ứng với cùng một góc của bức hình với điểm \((x_1, y_1)\) trong tam giác thứ hai, và tương tự cho \((x_2, y_2)\) và \((x_3, y_3)\).

Dữ liệu ra

Với mỗi bộ test, hãy xuất một dòng chứa "Case #\(x\): " theo sau là hai số thực biểu diễn tọa độ của điểm trùng nhau cách nhau bởi một dấu cách, hoặc chuỗi "No Solution". Các câu trả lời có sai số tương đối hoặc tuyệt đối không quá \(10^{-5}\) sẽ được coi là chính xác.

Ràng buộc

• \(1 \le N \le 10\).
• Tọa độ của các điểm sẽ là các số nguyên nằm trong khoảng từ \(-10\,000\) đến \(10\,000\). Ba điểm trong mỗi tam giác sẽ không thẳng hàng.

Phân nhóm

• Small dataset (Test set 1 - Visible): Tất cả các bộ test sẽ chứa các tam giác vuông cân (tức là các góc của tam giác sẽ là 45 độ, 45 độ và 90 độ).
• Large dataset (Test set 2 - Hidden): Các tam giác có thể có hình dạng bất kỳ.

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

2
0 0 0 2 2 0
0 0 0 1 1 0
10 0 0 10 0 0
3 3 1 1 3 1

Case #1: 0.000000 0.000000
Case #2: 2.692308 1.538462

Nguồn

Google Code Jam 2008, Vòng bán kết EMEA, bài Scaled Triangle.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.