题目描述

交并比，又称雅卡尔指数或雅卡尔相似系数（法语原文 coefficient de communauté，由 Paul Jaccard 提出），是用于比较样本集的相似性与多样性的统计量。雅卡尔系数能够量度有限样本集合的相似度，其定义为两个集合交集大小与并集大小之间的比例：

在计算机视觉中，交并比（IOU）是一个被广泛使用的统计量，用于衡量各类对象检测和分割算法。

与 x 轴和 y 轴对齐的矩形（即矩形的边与 x 轴或 y 轴平行）通常被称作“轴对齐矩形”，“轴对齐矩形边界框”（AABB），或 “边界框”。另一方面，与 x 轴和 y 轴不一定对齐的矩形（即矩形的边与坐标轴可能成一个角度）通常被成为“旋转矩形”，“旋转矩形边界框”，或“方向矩形边界框”（OBB）。在计算机视觉与图像处理应用中，根据需要解决的问题，两种矩形都被广泛使用。

本题中，您需要找到一个轴对齐矩形（AABB），使得它与一个旋转矩形（OBB）的交并比最大。两个矩形之间的交并比定义为两个矩形交集的面积除以两个矩形并集的面积。

输入格式

有多组测试数据。第一行输入一个整数 $T$（$1 \le T \le 10^4$）表示测试数据组数，对于每组测试数据：

第一行输入八个整数 $x_1$，$y_1$，$x_2$，$y_2$，$x_3$，$y_3$，$x_4$，$y_4$（$-10^9 \le x_i, y_i \le 10^9$），其中 $(x_i, y_i)$ 表示旋转矩形的第 $i$ 个顶点的坐标。顶点以顺时针或逆时针顺序给定。保证旋转矩形的面积为正。

输出格式

每组数据输出一行一个数表示旋转矩形和轴对齐矩形之间的最大交并比。如果相对误差或绝对误差不超过 $10^{-9}$，您的答案将被接受。

3
0 2 2 0 0 -2 -2 0
7 -2 9 -2 9 2 7 2
7 13 11 10 5 2 1 5

0.70710678118654752
1
0.62384322483109367

提示

样例数据解释如下。输入的矩形用点状阴影表示，最优的轴对齐矩形用斜线阴影表示。

:::align{center} :::