CF1059D - Nature Reserve

该死的精度问题让我调了一个小时还没有调出来(事实说明我还是太菜了。)

大概意思就是说平面上给了你一些点然后你要构造一个与 x 轴相切的圆把这些圆都包裹进去。

考虑二分圆的半径,这样就知道了圆心的 y 坐标,根据点在圆内的充要条件——点到圆心的距离小于等于半径计算出圆心的 x 坐标的范围。如果存在两个范围不相交,说明无法构造出一个符合条件的圆心。

需要注意浮点数运算的精度问题,比如计算 x 坐标的范围时这么写:

1
dis = r * r - (r - y) * (r - y);

就容易被卡,而:

1
dis = 2 * r * y - y * y;

就不容易。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×