思路:先考虑在D高度的最小圆覆盖，再一层一层往下走时，可以保证圆心与最开始的圆相同的时候答案是最优的。

时间复杂度O(n)

有一个坑点，就是我用了srand（time(NULL))就T了，RP太差了。。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           const double eps=1e-8;const double inf=1e60;const double Pi=acos(-1);struct Point{ double x,y; Point(){} Point(double x0,double y0):x(x0),y(y0){}}p[500005],O;struct Line{ Point s,e; Line(){} Line(Point s0,Point e0):s(s0),e(e0){}};Point operator -(Point p1,Point p2){ return Point(p1.x-p2.x,p1.y-p2.y);}Point operator +(Point p1,Point p2){ return Point(p1.x+p2.x,p1.y+p2.y);}Point operator *(Point p,double x){ return Point(p.x*x,p.y*x);}Point operator /(Point p,double x){ return Point(p.x/x,p.y/x);}double operator *(Point p1,Point p2){ return p1.x*p2.y-p1.y*p2.x;}double sqr(double x){ return x*x;}double dis(Point p1){ return sqrt(sqr(p1.x)+sqr(p1.y));}double dis(Point p1,Point p2){ return dis(p1-p2);}int n;double cost[500005],D,R;int H;int read(){ int t=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){ if (ch=='-') f=-1;ch=getchar();} while ('0'<=ch&&ch<='9'){t=t*10+ch-'0';ch=getchar();} return t*f;}Point inter(Line p1,Line p2){ double k1=(p2.e-p1.s)*(p1.e-p1.s); double k2=(p1.e-p1.s)*(p2.s-p1.s); double t=(k2)/(k1+k2); double x=p2.s.x+(p2.e.x-p2.s.x)*t; double y=p2.s.y+(p2.e.y-p2.s.y)*t; return Point(x,y);}Point turn(Point p,double ang){ double Cos=cos(ang); double Sin=sin(ang); double x=Cos*p.x-Sin*p.y; double y=Cos*p.y+Sin*p.x; return Point(x,y);}Point calc(Point p1,Point p2,Point p3){ Point a=(p1+p2)/2.0; Point b=(p2+p3)/2.0; Point A=turn(p2-p1,Pi/2.0)+a; Point B=turn(p3-p2,Pi/2.0)+b; return inter(Line(a,A),Line(b,B));}int main(){ //srand(time(NULL)); int DD; n=read();H=read();scanf("%lf",&R);DD=read(); D=DD; for (int i=0;i<=H;i++) cost[i]=read(); for (int i=1;i<=n;i++) p[i].x=read(),p[i].y=read(); for (int i=1;i<=n;i++) std::swap(p[rand()%n+1],p[rand()%n+1]); O=p[1];double r=0; for (int i=2;i<=n;i++) if (dis(O,p[i])>r+eps){ O=p[i];r=0; for (int j=1;j
           
            r+eps){ O=(p[i]+p[j])/2.0; r=dis(O,p[j]); for (int k=1;k
            
             r+eps){ O=calc(p[i],p[j],p[k]); r=dis(O,p[k]); } } } double ans=inf,rr,xx,yy; int hh; H=std::min(H,DD); for (int i=0;i<=H;i++){ double sxr=std::max(R,r-sqrt(sqr(D)-sqr((double)i))); if (sxr*cost[i]