BASIC-18VIP试题 矩形面积交判断 线段交

时间:2024-05-03 01:54:54来源:天理良心网 作者:知识

BASIC-18VIP试题 矩形面积交判断 线段交

在 X-Y 坐标平面上,试题给定多个矩形,矩形交判它们的面积边分别与坐标轴平行。请计算它们的断线段交并的面积。 输入格式输入第一行为一个整数 n,试题1<=n<=100,矩形交判表示矩形的面积数量。接下来有 n 行,断线段交每行包括四个数:x1,试题y1,x2,y2 (0<=x1<x2<=100000;0<=y1<y2<=100000),用空格分开,矩形交判不一定为整数。面积(x1,断线段交y1)表示一个长方形的左下顶点坐标,(x2,试题y2)表示右上顶点坐标。 输出格式n个矩形的矩形交判并的面积,保留两位小数。面积 输入样例20 0 2 2 1 1 3 3 输出样例7.00Hint此题没能用上递归、分治或其他等一系列方法。以下为推荐思路,鼓励自行思考别的方法。第一题本为练笔,但我挑选的此题似乎实现起来麻烦。对不住大家了!若实在觉得繁琐的可跳过此题。:(但,练练手总没坏处滴 :)多个矩形面积重叠没有规律,难以直接求解或用上递归的思路。只能从矩形重叠的情况入手,进行局部相加。1)将所有矩形的左右边界都投影到X轴上,形成各个区间2)从左向右计算每个区间,将落在该区间内的矩形进行面积统计3)将每个区间计算的面积再相加
相关内容
推荐内容