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

投影仪由位于原点 的点光源,以及透镜平面上的一个矩形描述。设透镜矩形的宽为 ,高为 ,则希望得到的画面宽高比为 。光线从原点出发,穿过透镜矩形,再投到墙面上;墙上有一个矩形幕布。
Haru 可以在透镜矩形内部或边界上选取四个锚点,使它们的投影满足:
- 投影后的四个点组成一个矩形,水平宽与竖直高的比例恰好为 。
- 该矩形的底边与 平面平行。这里底边是两条水平边中 坐标较小的一条。
- 整个投影矩形都落在幕布内部或边界上。
求这样的投影矩形的最大面积。锚点不要求为整数点。
下图展示了梯形校正和最终结果,对应第一个样例的一种最优方案。左侧绿色四边形是透镜矩形中实际使用的区域,右侧绿色矩形是最终投影。

输入格式
第一行一个整数 ,表示测试用例数。
每个测试用例包含八行:
- 前四行中,第 行给出三个整数 ,表示透镜矩形的第 个顶点。
- 后四行中,第 行给出三个整数 ,表示幕布矩形的第 个顶点。
两个矩形的四个顶点均按“左下、右下、右上、左上”的顺序给出。透镜宽 是第 个顶点的距离,高 是第 个顶点的距离。
输出格式
每个测试用例输出一行一个十进制实数,表示最大面积。设真实答案为 ,输出值为 ,当
时认为答案正确,即绝对误差或相对误差不超过 。
数据范围与保证
- 。
- 透镜顶点满足 ,。
- 透镜满足 ,。
- 幕布顶点满足 ,。
- 幕布满足 ,,,。两组 之间不要求大小关系。
- 每组四个顶点确实构成一个矩形,且 。
- 墙面与 平面垂直,幕布底边与 平面平行。
- 透镜矩形与原点位于墙面的同一侧,并且它们到墙面的距离均至少为 。
- 透镜矩形所在平面到原点的距离至少为 。
- 幕布底边与 轴的夹角不超过 ;透镜底边与 轴的夹角也不超过 。
- 未校正光束在墙面上照亮的面积不超过 。
- 幕布与未校正投影的交集面积至少为 。
样例
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