链接
题意
如图,给出在格点上的凸多边形,输出面积最大的边与坐标轴平行的矩形的面积。
思路
首先,最大矩形的面积为矩形宽度的上凸函数。然后,对于指定宽度的矩形,矩形的面积为左边界的位置的上凸函数。给出指定的位置可以求出当前位置与多边形交点的$y$值。因此可以使用三分套三分套二分的方式解决这道题。
UVa 1679 - Easy Geometry和这个是同一道题,不过好像题的数据有问题,NEERC官方题解中tourist的代码也过不了。
代码
|
|
A little brute force is always helpful.
如图,给出在格点上的凸多边形,输出面积最大的边与坐标轴平行的矩形的面积。
首先,最大矩形的面积为矩形宽度的上凸函数。然后,对于指定宽度的矩形,矩形的面积为左边界的位置的上凸函数。给出指定的位置可以求出当前位置与多边形交点的$y$值。因此可以使用三分套三分套二分的方式解决这道题。
UVa 1679 - Easy Geometry和这个是同一道题,不过好像题的数据有问题,NEERC官方题解中tourist的代码也过不了。
|
|