[ICPC 2018 Shenyang Onsite L][Gym 101955L]Machining Disc Rotors

Link

Solution

最远点对一定出现在一对交点处,或者交点和它的未被覆盖的对称点处。考虑弦长变化的单调性即可证明。

Code

const int XN=2e2+11;
const double eps=1e-10,pi=acos(-1);

int sgn(double const &x) {
    return (x>-eps)-(x<eps);
}

struct Point {
    double x,y;

    double Length() const {
        return sqrt(x*x+y*y);
    }

    Point Normal() const {
        return Point{-y,x};
    }

    Point Unit() const {
        double len=Length();
        return Point{x/len,y/len};
    }

    friend Point operator +(const Point &a,const Point &b) {
        return Point{a.x+b.x,a.y+b.y};
    }

    friend Point operator -(const Point &a,const Point &b) {
        return Point{a.x-b.x,a.y-b.y};
    }

    friend Point operator *(const Point &a,const double &k) {
        return Point{a.x*k,a.y*k};
    }

    friend Point operator /(const Point &a,const double &k) {
        return Point{a.x/k,a.y/k};
    }

    friend double Inner(const Point &a,const Point &b) {
        return a.x*b.x+a.y*b.y;
    }

    friend double Outer(const Point &a,const Point &b) {
        return a.x*b.y-a.y*b.x;
    }
};

double Dist(const Point &a,const Point &b) {
    return (a-b).Length();
}

void Work() {
    int n,R;fin>>n>>R;
    Point o{0,0};
    auto Atan2=[](double const &y,double const &x) { double r=atan2(y,x); return r<0?r+pi*2:r; };
    bool flag=0;
    auto Calc=[&](Point p,int r)->std::vector<Point> {
        int d1=sgn(Dist(o,p)-R-r),d2=sgn(Dist(o,p)-fabs(R-r));
        if(d1==0)
            return {p/(R+r)*R};
        else if(d1<0 && d2==0) {
            return {p/(R-r)*R};
        } else if(d1<0 && d2>0) {
            double d=Dist(o,p),x=(R*R-r*r+d*d)/(2*d),h=sqrt(R*R-x*x);
            Point v=(p-o).Unit(),n=v.Normal();
            return {v*x-n*h,v*x+n*h};
        } else
            return {};
    };

    std::vector<Point> cross;
    std::vector<std::pair<double,double> > ranges;
    for(int i=1;i<=n;++i) {
        int x,y,r;
        fin>>x>>y>>r;
        std::vector<Point> nc=Calc(Point{(double)x,(double)y},r);
        for(Point &p : nc)
            cross.push_back(p);
        if(nc.size()==1) {
            double x=Atan2(nc[0].y,nc[0].x);
            ranges.push_back({x,x});
        } else if(nc.size()==2)
            ranges.push_back({Atan2(nc[0].y,nc[0].x),Atan2(nc[1].y,nc[1].x)});
    }
    std::sort(ranges.begin(),ranges.end());
    double Ans=0;
    for(size_t i=0;i<cross.size();++i) {
        for(size_t j=i+1;j<cross.size();++j)
            Enlarge(Ans,Dist(cross[i],cross[j]));
        double ang=Atan2(-cross[i].y,-cross[i].x);
        auto Cover=[&](std::pair<double,double> const &x,double const &y)->bool {
            if(x.first<=x.second)
                return x.first<=y && y<=x.second;
            else
                return x.first<=y || y<=x.second;
        };
        auto iter=std::upper_bound(ranges.begin(),ranges.end(),std::pair<double,double>(ang,ang));
        if(iter!=ranges.begin())
            flag|=!Cover(*--iter,ang) && !Cover(ranges.back(),ang);
        else
            flag|=!Cover(ranges.back(),ang);
        if(flag)
            break;
    }
    if(flag)
        Ans=R*2;
    fout<<Ans<<'\n';
}

int main() {
    int T;fin>>T;
    for(int ks=1;ks<=T;++ks) {
        printf("Case #%d: ",ks);
        Work();
    }
    return 0;
}