#P18447. Intersection over Union
Intersection over Union
Intersection over Union
输入:标准输入;输出:标准输出。
交并比(Intersection over Union,简称 IOU)也称 Jaccard 指数或 Jaccard 相似系数,最初由 Paul Jaccard 提出,法语名为 coefficient de communauté。它用于衡量样本集合之间的相似性和差异性。对于有限集合 ,定义
IOU 也是计算机视觉中评估目标检测、图像分割等算法的常用指标。
边分别平行于 轴、 轴的矩形,通常称为轴对齐矩形、轴对齐包围框(AABB),或简称 bounding box。边不一定与坐标轴平行的矩形,通常称为旋转矩形、旋转包围框或有向包围框(OBB)。这两种矩形都广泛用于计算机视觉和图像处理。
本题给定一个旋转矩形 OBB,请选择一个轴对齐矩形 AABB,使两者的 IOU 最大。两个矩形的 IOU 定义为:交集面积除以并集面积。
输入格式
第一行包含整数 (),表示测试用例数。
每个测试用例仅有一行,包含八个整数
其中 表示旋转矩形的第 个顶点,顶点按顺时针或逆时针顺序给出。坐标满足
保证所给矩形面积为正。
输出格式
对于每个测试用例输出一行,一个数,表示能达到的最大 IOU。
如果答案的绝对误差或相对误差不超过 ,则认为正确。要求输出的是最大 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
原样例说明
下图展示了三个原样例。点阵填充区域是输入的旋转矩形,斜线填充区域是最优轴对齐矩形。
