XJOI网上同步测试DAY14 T2

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

时间复杂度O(n)

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

#include<cstdio>

#include<cmath>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<time.h>

const double eps=1e-;

const double inf=1e60;

const double Pi=acos(-);

struct Point{

    double x,y;

    Point(){}

    Point(double x0,double y0):x(x0),y(y0){}

}p[],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[],D,R;

int H;

int read(){

    int t=,f=;char ch=getchar();

    while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}

    while (''<=ch&&ch<=''){t=t*+ch-'';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=;i<=H;i++) cost[i]=read();

    for (int i=;i<=n;i++) p[i].x=read(),p[i].y=read();

    for (int i=;i<=n;i++)

     std::swap(p[rand()%n+],p[rand()%n+]);

    O=p[];double r=;

    for (int i=;i<=n;i++)

     if (dis(O,p[i])>r+eps){

        O=p[i];r=;

        for (int j=;j<i;j++)

         if (dis(O,p[j])>r+eps){

            O=(p[i]+p[j])/2.0;

            r=dis(O,p[j]);

            for (int k=;k<j;k++)

             if (dis(O,p[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=;i<=H;i++){

        double sxr=std::max(R,r-sqrt(sqr(D)-sqr((double)i)));

        if (sxr*cost[i]<ans){

            ans=sxr*cost[i];

            rr=sxr;

            xx=O.x;

            yy=O.y;

            hh=i;

        }

    }

    printf("%.10f\n",ans);

    printf("%.10f %.10f %d %.10f\n",xx,yy,hh,rr);

}