#P3621. 我想那还真是令人高兴啊

    ID: 1777 传统题 1000ms 128MiB 尝试: 265 已通过: 98 难度: 6 上传者: 标签>难度分类普及+/提高-枚举与搜索排列枚举数论同余的加减乘运算计算几何复数表示旋转与缩放CF19002014湖北省队互测week2

我想那还真是令人高兴啊

我想那还真是令人高兴啊

题目描述

Mami 在保护 QB 的过程中认识了 Madoka 和 Sayaka,并邀请她们一起去看她消灭 Gertrud。

Gertrud 知道 Mami 的实力,便藏进废弃工厂里的两个三角形结界。Mami 已经取得两组三角形顶点的坐标,发现其中一个三角形可以由另一个绕某个中心旋转并按同一比例缩放得到。这个中心正是 Gertrud 的藏身处。请根据两组三角形求出中心坐标。

输入格式

第一行一个整数 TT,表示数据组数。每组包含两行。

  • 第一行六个实数 x1,y1,x2,y2,x3,y3x_1,y_1,x_2,y_2,x_3,y_3,表示第一个三角形的三个顶点。
  • 第二行六个实数 x4,y4,x5,y5,x6,y6x_4,y_4,x_5,y_5,x_6,y_6,表示第二个三角形的三个顶点。

两个三角形相似,第二个三角形位于第一个三角形之内,允许边界重合。坐标精度为小数点后六位。

输出格式

每组输出一行,包含两个用空格隔开的实数,表示中心的横坐标与纵坐标。对一个能使三个顶点全部对应的旋转缩放中心,横、纵坐标分别满足绝对误差小于 10−310^{-3} 或相对误差小于 10−310^{-3} 即可。若存在多个合法中心,输出任意一个;两组三角形完全重合时,恒等变换对任意中心成立,因此任意有限坐标均可。

样例

2

0.00 0.00 3.00 0.00 0.00 3.00
1.00 1.00 2.00 1.00 1.00 2.00
10.00 0.00 0.00 10.00 0.00 0.00
1.00 1.00 3.00 1.00 3.00 3.00
1.500000 1.500000
2.692308 1.538462

数据范围

  • 对于 20%20\% 的数据,没有旋转。
  • 对于所有数据,T≤10T\le10,∣xi∣,∣yi∣≤10000|x_i|,|y_i|\le10000。