NEERC 2007 Feng Shui

题意:给定一个凸多边形,现在要将两个半径相同的圆地毯放入多边形。地毯可以重叠但边缘不能与多边形相交。要使地毯覆盖的面积最大,输出一种最大方案的圆心坐标。

半平面交经典题,把边缘向内收缩r做半平面交,然后算最远的两个点。

发表评论

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