人们历经磨难,终于找到了著名海盗Guybrush Threepwood藏匿宝箱的金银岛。虽然已经知道Guybrush肯定把宝箱藏在了此岛,但具体的藏匿位置仍然不得而知。快要翻遍整个小岛时,发现了地图上未能标出的写有宝箱埋藏位置的纸条。纸条对宝箱的位置进行了详细说明,不过,因为写得过于繁琐,而且有多处字迹已经无法辨认,无法获知准确信息。经过认真研究,人们最终还是把寻宝范围缩小了一些。 如图所示,小岛由具有N个顶点的多边形构成。藏宝位置的范围是,以两个点(x1, y1)和(x2, y2)为对角顶点、4条边与x轴和y轴相互平行的矩形内部。现在想调查该矩形内部的陆地部分,试编写程序计算此部分面积。 时间及内存使用限制 程序必须在1秒内完成运算,使用内存不得超过64MB。 输入 第一行输入测试用例的个数C(C≤50)。各测试用例的第一行输入5个整数,表示矩形的两个顶点坐标x1、y1、x2、y2(0≤x1<x2≤100、0≤y1<y2≤100)和表示小岛轮廓的多边形的顶点个数N(3≤N≤100)。之后的N行中,每行输入两个整数,表示每个顶点的两个坐标xi、yi(0≤xi、yi≤100)。顶点坐标会按照逆时针方向输入,最后一个点与第一个点相连。 不存在给出的岛屿面积为0,或小岛的边自相交叉或重叠的情况。 输出 每个测试用例在1行内输出需要调查的陆地面积。允许小于107的绝对/相对误差。 示例输入值 2 26 34 76 72 15 41 52 50 71 42 87 26 84 16 58 33 33 51 23 64 32 73 17 86 14 91 38 92 68 82 79 68 45 61 58 50 20 70 80 4 86 50 30 10 90 50 30 90 示例输出值 1343.0948739496 57.1428571429