[ICPC 2018 Asia Yokohama Onsite F]Fair Chocolate Cutting

Link

Solution

最长的距离,貌似一定一端在顶点上。
最短的距离,固定一个端点在一条边上,那么这条平分线的长度貌似应该是单峰的。
然后就扫一遍,三分三分,就OK了。
然而正解……

Code

const int XN=5000+11;
const long double inf=1e100;

struct Point {
    long double x,y;

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

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

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

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

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

    friend long double Dist(Point const &a,Point const &b) {
        return sqrt(Inner(a-b,a-b));
    }
}p[XN];

long double Length(Point a,Point b,long double t,Point c,Point d,long double size) {
    //a+(b-a)*t 在cd上找 让bd部分为size的线
    Point v=a+(b-a)*t;
    long double req=(Outer(b-a,c-a)+Outer(c-a,d-a))/2-size-Outer(v-a,d-a)/2;
    //(v-d) x (t*(c-d))=2*size
    long double l=2*req/Outer(v-d,c-d);
    return Dist(v,d+(c-d)*l);
}

long double SolveMin(Point a,Point b,Point c,Point d,long double size) {
    long double l=0,r=1;
    while(r-l>1e-15) {
        long double m1=l+(r-l)/3,m2=r-(r-l)/3;
        if(Length(a,b,m1,c,d,size)>Length(a,b,m2,c,d,size))
            l=m1;
        else
            r=m2;
    }
    return Length(a,b,l,c,d,size);
}

int main() {
    freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int n;std::cin>>n;
    for(int i=0;i<n;++i)
        std::cin>>p[i].x>>p[i].y;
    long double size=0;
    for(int i=2;i<n;++i)
        size+=Outer(p[i-1]-p[0],p[i]-p[0]);

    size/=2;

    long double AnsMax=-inf,AnsMin=inf,sum=0;
    for(int l=0,r=1;l<n;sum-=Outer(p[(l+1)%n]-p[l],p[r]-p[l])/2,++l) {
        for(long double d=0;sum+(d=Outer(p[r]-p[l],p[(r+1)%n]-p[l])/2)<size/2;sum+=d,(r+=1)%=n);
        Enlarge(AnsMax,Length(p[l],p[l],0,p[r],p[(r+1)%n],size/2-sum));
        Reduce(AnsMin,SolveMin(p[l==0?n-1:l-1],p[l],p[r],p[(r+1)%n],size/2-sum));
    }
    std::cout<<std::fixed<<std::setprecision(10)<<AnsMin<<'\n'<<AnsMax<<'\n';
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注