Description

给定两幅三角形图片。第二幅图片是第一幅图片经过平移、旋转和缩放（缩放比例严格在 $0$ 和 $1$ 之间）后得到的版本。两个三角形被放置在桌面上，第二个三角形完全位于第一个三角形内部（可能与边界接触）。

你需要处理这幅图片，找到一个点，使得该点在原图和缩放后的图片中重合。如果有多个解，可以输出任意一个。如果没有解，则输出 "No Solution"。

Input Format

第一行输入一个整数 $N$，表示测试用例的数量。接下来每个测试用例包含两行，每行包含六个用空格分隔的整数，表示一个三角形的三个顶点坐标，格式为 "$x_1$ $y_1$ $x_2$ $y_2$ $x_3$ $y_3$"。第一个三角形的 $(x_1, y_1)$ 与第二个三角形的 $(x_1, y_1)$ 对应，$(x_2, y_2)$ 与 $(x_2, y_2)$ 对应，$(x_3, y_3)$ 与 $(x_3, y_3)$ 对应。

Output Format

对于每个测试用例，输出一行，格式为 "Case #$x$: "，后接两个实数，表示重合点的坐标，用一个空格分隔；如果没有解，则输出 "No Solution"。只要相对或绝对误差不超过 $10^{-5}$，答案即视为正确。

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

Hint

数据范围

• $1 \leqslant N \leqslant 10$。
• 坐标均为 $-10\,000$ 到 $10\,000$ 之间的整数。每个三角形的三个点不会共线。

小数据（测试集 1 - 可见）

• 所有测试用例均为等腰直角三角形（即三角形的角分别为 $45^\circ$、$45^\circ$ 和 $90^\circ$）。

大数据（测试集 2 - 隐藏）

• 三角形可以为任意形状。

由 ChatGPT 4.1 翻译