2491. Scaled Triangle

单点时限: 2.0 sec

内存限制: 256 MB

You are given two triangle-shaped pictures. The second picture is a possibly translated, rotated and scaled version of the first. The two triangles are placed on the table, with the second one placed completely inside (possibly touching the boundary of) the first one. The second triangle is always scaled by a factor that is strictly between 0 and 1.

You need to process the picture, and for that you need a point in the picture which overlaps with the same point of the scaled picture. If there is more than one solution, you can return any of them. If there are no solutions, print “No Solution” (without the quotes) for that test case.

输入格式

The first line of input gives the number of cases, N(1 <= N <= 10.). Then for each test case, there will be two lines, each containing six space-separated integers – the coordinates of one of the triangles – in the format “x1 y1 x2 y2 x3 y3”. The point (x1, y1) in the first triangle corresponds to the same corner of the picture as (x1, y1) in the second triangle, and similarly for (x2, y2) and (x3, y3).

The coordinates of the points will be integer numbers between -10 000 and 10 000. The three points in each triangle will not be collinear. The triangles can have any shape.

输出格式

For each test case, output one line containing “Case #x: ” followed two real numbers representing the coordinates of the overlapping point separated by one space character, or the string “No Solution”. Answers with a relative or absolute error of at most 10-5 will be considered correct.

样例

Input
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
Output
Case #1: 0.000000 0.000000
Case #2: 2.692308 1.538462

0 人解决,1 人已尝试。

0 份提交通过,共有 1 份提交。

9.9 EMB 奖励。

创建: 15 年,3 月前.

修改: 6 年,9 月前.

最后提交: 3 年,6 月前.

来源: GCJ 2008

题目标签