查字典图书网
查字典图书网
人们历经磨难，终于找到了著名海盗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