BZOJ【2338】画矩形

这题要求找出一个最大面积的矩形,学过数学的都知道:矩形对角线交于一点,而且两条对角线相等。于是我们就可以枚举每一条线段,按长度排序,取长度相等的判断他们的中点是否重合,重合的话就可以构成一个矩形。

按照上面的方法,枚举线段要n^2, 排序要n^2log(n^2),所以时间大概为O(n^2log(n^2))。

但是这题的数据有10^8,如果用两点之间距离公式和中点公式有可能被卡精度,于是可以在求距离是不开根号,直接用long long存,中点公式也不除2,这样可以避免精度的影响。

最后,在求面积时用叉积求即可。

发表评论

电子邮件地址不会被公开。 必填项已用*标注