D-现在是,学术时间 (II)_2023牛客寒假算法基础集训营1 (nowcoder.com)
给一个矩形 和一个点 , 再找一个点与 组成另一个矩形, 求 的最大值。
为了让并集面积尽量小, 新点的选择要从矩形的边中选, 这样就可以直接枚举。然后根据枚举出的点计算两个矩形的交集面积和并集面积求解即可。
并集面积可以在求出交集面积后, 将两个矩形面积相加再减去交集面积。 求交集面积需要先找出 即两个矩形左侧边的最小值, 右侧边的最大值, 上侧边的最小值, 下侧边的最大值。然后再求面积。
D-现在是,学术时间 (II)_2023牛客寒假算法基础集训营1 (nowcoder.com)
给一个矩形 和一个点 , 再找一个点与 组成另一个矩形, 求 的最大值。
为了让并集面积尽量小, 新点的选择要从矩形的边中选, 这样就可以直接枚举。然后根据枚举出的点计算两个矩形的交集面积和并集面积求解即可。
并集面积可以在求出交集面积后, 将两个矩形面积相加再减去交集面积。 求交集面积需要先找出 即两个矩形左侧边的最小值, 右侧边的最大值, 上侧边的最小值, 下侧边的最大值。然后再求面积。