#P18447. Intersection over Union

Intersection over Union

Intersection over Union

输入:标准输入;输出:标准输出。

交并比(Intersection over Union,简称 IOU)也称 Jaccard 指数或 Jaccard 相似系数,最初由 Paul Jaccard 提出,法语名为 coefficient de communauté。它用于衡量样本集合之间的相似性和差异性。对于有限集合 A,BA,B,定义

J(A,B)=∣A∩B∣∣A∪B∣.J(A,B)=\frac{|A\cap B|}{|A\cup B|}.

IOU 也是计算机视觉中评估目标检测、图像分割等算法的常用指标。

边分别平行于 xx 轴、yy 轴的矩形,通常称为轴对齐矩形、轴对齐包围框(AABB),或简称 bounding box。边不一定与坐标轴平行的矩形,通常称为旋转矩形、旋转包围框或有向包围框(OBB)。这两种矩形都广泛用于计算机视觉和图像处理。

本题给定一个旋转矩形 OBB,请选择一个轴对齐矩形 AABB,使两者的 IOU 最大。两个矩形的 IOU 定义为:交集面积除以并集面积。

输入格式

第一行包含整数 TT(1≤T≤1041\le T\le10^4),表示测试用例数。

每个测试用例仅有一行,包含八个整数

x1,y1,x2,y2,x3,y3,x4,y4,x_1,y_1,x_2,y_2,x_3,y_3,x_4,y_4,

其中 (xi,yi)(x_i,y_i) 表示旋转矩形的第 ii 个顶点,顶点按顺时针或逆时针顺序给出。坐标满足

−109≤xi,yi≤109.-10^9\le x_i,y_i\le10^9.

保证所给矩形面积为正。

输出格式

对于每个测试用例输出一行,一个数,表示能达到的最大 IOU。

如果答案的绝对误差或相对误差不超过 10−910^{-9},则认为正确。要求输出的是最大 IOU 数值,不需要输出所选择矩形的坐标。

原样例

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

原样例说明

下图展示了三个原样例。点阵填充区域是输入的旋转矩形,斜线填充区域是最优轴对齐矩形。

原题三个样例中的点阵 OBB 和斜线最优 AABB