#P18271. Keystone Correction

Keystone Correction

Keystone Correction

题目描述

喜欢动画的 Haru 买了一台便宜的投影仪,希望在家中的墙上观看大画面。不过,这台投影仪固定在支架上,调节功能有限,画面经常出现偏斜。它支持手动梯形校正:在透镜矩形内选出四个锚点,以它们确定要投射的四边形区域,使最终画面成为符合要求的矩形。

下图是投影未校正时的示意。

原题:未校正的投影

投影仪由位于原点 O=(0,0,0)O=(0,0,0) 的点光源,以及透镜平面上的一个矩形描述。设透镜矩形的宽为 ww,高为 hh,则希望得到的画面宽高比为 w:hw:h。光线从原点出发,穿过透镜矩形,再投到墙面上;墙上有一个矩形幕布。

Haru 可以在透镜矩形内部或边界上选取四个锚点,使它们的投影满足:

  • 投影后的四个点组成一个矩形,水平宽与竖直高的比例恰好为 w:hw:h。
  • 该矩形的底边与 xOyxOy 平面平行。这里底边是两条水平边中 zz 坐标较小的一条。
  • 整个投影矩形都落在幕布内部或边界上。

求这样的投影矩形的最大面积。锚点不要求为整数点。

下图展示了梯形校正和最终结果,对应第一个样例的一种最优方案。左侧绿色四边形是透镜矩形中实际使用的区域,右侧绿色矩形是最终投影。

原题:梯形校正及最终投影

输入格式

第一行一个整数 TT,表示测试用例数。

每个测试用例包含八行:

  • 前四行中,第 ii 行给出三个整数 xi,yi,zix_i,y_i,z_i,表示透镜矩形的第 ii 个顶点。
  • 后四行中,第 ii 行给出三个整数 ui,vi,wiu_i,v_i,w_i,表示幕布矩形的第 ii 个顶点。

两个矩形的四个顶点均按“左下、右下、右上、左上”的顺序给出。透镜宽 ww 是第 1,21,2 个顶点的距离,高 hh 是第 1,41,4 个顶点的距离。

输出格式

每个测试用例输出一行一个十进制实数,表示最大面积。设真实答案为 AA,输出值为 XX,当

∣X−A∣≤10−6max⁡(1,∣A∣)|X-A|\le10^{-6}\max(1,|A|)

时认为答案正确,即绝对误差或相对误差不超过 10−610^{-6}。

数据范围与保证

  • 1≤T≤10001\le T\le1000。
  • 透镜顶点满足 ∣xi∣,∣zi∣≤100|x_i|,|z_i|\le100,1≤yi≤1001\le y_i\le100。
  • 透镜满足 max⁡(x1,x4)<min⁡(x2,x3)\max(x_1,x_4)<\min(x_2,x_3),max⁡(z1,z2)<min⁡(z3,z4)\max(z_1,z_2)<\min(z_3,z_4)。
  • 幕布顶点满足 ∣ui∣,∣wi∣≤1000|u_i|,|w_i|\le1000,max⁡1≤j≤4yj<vi≤1000\max_{1\le j\le4}y_j<v_i\le1000。
  • 幕布满足 u1=u4<u2=u3u_1=u_4<u_2=u_3,v1=v4v_1=v_4,v2=v3v_2=v_3,w1=w2<w3=w4w_1=w_2<w_3=w_4。两组 vv 之间不要求大小关系。
  • 每组四个顶点确实构成一个矩形,且 1≤w/h≤41\le w/h\le4。
  • 墙面与 xOyxOy 平面垂直,幕布底边与 xOyxOy 平面平行。
  • 透镜矩形与原点位于墙面的同一侧,并且它们到墙面的距离均至少为 11。
  • 透镜矩形所在平面到原点的距离至少为 11。
  • 幕布底边与 xx 轴的夹角不超过 π/18=10∘\pi/18=10^\circ;透镜底边与 xx 轴的夹角也不超过 10∘10^\circ。
  • 未校正光束在墙面上照亮的面积不超过 10610^6。
  • 幕布与未校正投影的交集面积至少为 11。

样例

2
-20 23 -36
20 23 -36
20 41 -12
-20 41 -12
-50 80 -100
50 79 -100
50 79 -20
-50 80 -20
-1 2 4
1 2 4
1 3 5
-1 3 5
-20 6 0
20 6 0
20 6 20
-20 6 20
5450.0656584647
5.6568542495