QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#1303#827506#9576. Ordainer of Inexorable JudgmentLcyanstarsLcyanstarsSuccess!2024-12-23 14:23:132024-12-23 14:23:13

Details

Extra Test:

Wrong Answer
time: 0ms
memory: 4172kb

input:

3 10000 -1 500 6
501 1
501 10000
500 10000

output:

3.076372258785

result:

wrong answer 1st numbers differ - expected: '2.7931870', found: '3.0763723', error = '0.1013843'

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#827506#9576. Ordainer of Inexorable JudgmentLcyanstarsWA 1ms4408kbC++201.9kb2024-12-23 00:32:452024-12-23 14:28:43

answer

#include <bits/stdc++.h>

struct Point
{
    int x,y;
    Point(int _x=0,int _y=0):x(_x),y(_y){}
    Point operator -(Point a)
    {
        return {x-a.x,y-a.y};
    }
};

int cross(Point a,Point b)
{
    return a.x*b.y-a.y*b.x;
}

int cross(Point a,Point b,Point c)
{
    return cross(b-a,c-a);
}

int main()
{
    int n;
    Point p_0;
    double d,t;
    scanf("%d%d%d%lf%lf",&n,&p_0.x,&p_0.y,&d,&t);
    std::vector<Point> p(n);
    for(int i=0;i<n;i++)
        scanf("%d%d",&p[i].x,&p[i].y);
    bool ok=true;
    for(int i=0;i<n;i++)
        if(cross(p[i],p[(i+1)%n])<0)
            ok=false;
    if(ok)
    {
        printf("%.12lf\n",t);
        return 0;
    }
    const double pi=acos(-1),eps=1e-7;
    double mx=0,mn=2*pi;
    for(int i=0;i<n;i++)
    {
        double ang=atan2(p[i].y,p[i].x);
        if(ang<-eps)
            ang += 2*pi;
        mx=std::max(ang,mx);
        mn=std::min(ang,mn);
    }
    if(mx-mn >= pi-eps)
        ok=true;
    mx=0,mn=2*pi;
    for(int i=0;i<n;i++)
    {
        double L=sqrt(p[i].x*p[i].x+p[i].y*p[i].y);
        double del=asin(d/L);
        double ang=atan2(p[i].y,p[i].x);
        if(!ok && ang<-eps)
            ang += 2*pi; 
        double res[]{ang+del,ang-del};
        for(int j=0;j<2;j++)
        {
            mx=std::max(res[j],mx);
            mn=std::min(res[j],mn);
        }
    }
    int T=floor(t/(2*pi));
    t -= T*(2*pi);
    double ans=T*(std::min(mx-mn,2*pi));
    double ang=atan2(p_0.y,p_0.x);
    if(!ok && ang<-eps)
        ang += 2*pi;
    if(ang >= mn-eps && ang <= mx+eps)
    {
        ans += t;
        t -= std::min({std::max(mx-ang,0.0),t});
        ans -= t;
        ang=mx;
    }
    double tt=mn-ang;
    if(tt<-eps)
        tt += 2*pi;
    t -= tt;
    ans += std::max(std::min(t,mx-mn),0.0);
    printf("%.12lf\n",ans);
    return 0;
}