先把所有点绕原点逆时针旋转(360-a)度,再把所有点横坐标除以放大倍数p,最后用随机增量法求最小圆覆盖即可。
时间复杂度期望$O(n)$
#include#include #include using namespace std;struct P{double x,y;}a[50005],o;inline double dis(P x,P y){return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));}inline P center(P x,P y,P z){ double a1=y.x-x.x,b1=y.y-x.y,c1=(a1*a1+b1*b1)/2,a2=z.x-x.x,b2=z.y-x.y,c2=(a2*a2+b2*b2)/2,d=a1*b2-a2*b1; return (P){x.x+(c1*b2-c2*b1)/d,x.y+(a1*c2-a2*c1)/d};}double r,angle,e,x,y,eps=1e-8;int n,i,j,k;int main(){ srand(199745); for(scanf("%d",&n);i =r+eps)for(o=a[i],r=0,j=0;j =r)for(o=(P){(a[i].x+a[j].x)/2,(a[i].y+a[j].y)/2},r=dis(o,a[i]),k=0;k =r-eps)o=center(a[k],a[j],a[i]),r=dis(o,a[i]); printf("%.3lf",r); return 0;}