RT,本题唯一一篇题解亲测交到 AtCoder 上面会得到 WA 的结果,甚至连样例 2 都跑不过去。
5
0 0
2 0
0 2
2 2
1 1
本样例答案是 0,但是题解代码输出的是 4。
而究其根本原因,我们不难发现是本题解原有的翻译出了锅。
AtCoder 上的原题要求选取四个点组成的长方形的四条边要与坐标轴平行且长方形内部不能够包含任何点。因此样例 2 为什么输出 0 就很好解释了:我们选取样例中前四个点作为长方形的四个顶点,但是组成的长方形里面包含了第五个点,因此这个长方形不满足要求。而除此之外又再无其他的长方形满足要求了,因此答案是 0。
请求管理将这篇错误的题解和翻译撤下,本人在此帖中提供一个新的翻译。详情请见下划线下方内容。
翻译:
给定一个平面直角坐标系上的 n 个点,你需要从中选出 4 个点,使得以这四个点为顶点组成的长方形满足以下要求:
- 长方形的每条边都要与一条坐标轴平行。
- 长方形的内部(不包括边界)不能够包含给定的 n 个点中的一个或多个点。
求满足要求的所有长方形的面积的最大值。
Translated by Eason_AC
2021.7.21
源码:
给定一个平面直角坐标系上的 $n$ 个点,你需要从中选出 $4$ 个点,使得以这四个点为顶点组成的长方形满足以下要求:
- 长方形的每条边都要与一条坐标轴平行。
- 长方形的内部(**不包括边界**)不能够包含给定的 $n$ 个点中的一个或多个点。
Translated by Eason_AC
2021.7.21