QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#732886#9576. Ordainer of Inexorable JudgmentKIRITO1211#WA 0ms4280kbC++235.5kb2024-11-10 16:18:162024-11-10 16:18:17

Judging History

你现在查看的是最新测评结果

  • [2024-12-23 14:23:26]
  • hack成功,自动添加数据
  • (/hack/1303)
  • [2024-12-06 11:32:56]
  • hack成功,自动添加数据
  • (/hack/1271)
  • [2024-11-14 21:58:28]
  • hack成功,自动添加数据
  • (/hack/1181)
  • [2024-11-10 16:18:17]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4280kb
  • [2024-11-10 16:18:16]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define pf(x) ((x)*(x))
#define abs(x) ((x)>0?(x):-(x))
const double PI=acos(-1); 
const double eps=1e-9;
struct vec2
{
    double x,y;
    vec2(double x_,double y_):x(x_),y(y_){}
    vec2(){}
    vec2 operator-()
    {
        return vec2(-x,-y);
    }
    double len()
    {
        return sqrt(pf(x)+pf(y));
    }
    vec2 norm()
    {
        return vec2(x/len(),y/len());
    }
    void operator=(vec2 a)
    {
        x=a.x;
        y=a.y;
    }
    vec2 operator*(double xx)
    {
        return vec2(x*xx,y*xx);
    }
    vec2 Rrot(double ang)
    {
        return vec2(x*cos(ang)+y*sin(ang),y*cos(ang)-x*sin(ang));
    }
};
vec2 operator+(vec2 a,vec2 b)
{
    return vec2(a.x+b.x,a.y+b.y);
}
vec2 vmid(vec2 a,vec2 b)
{
    return vec2((a.x+b.x)/2.0,(a.y+b.y)/2.0);
}
double dist(vec2 a,vec2 b)
{
    return (a+(-b)).len();
}
typedef vec2 point;
double dot(vec2 a,vec2 b)
{
    return a.x*b.x+a.y*b.y;
}
double cross(vec2 a,vec2 b)
{
    return a.x*b.y-a.y*b.x;
}
double dis_seg(point a,point b)
{
    vec2 L=a,R=b;
    vec2 mid=vmid(L,R);
    double dl=L.len();
    double dr=R.len();
    while(dist(L,R)>eps)
    {
        if(dl<dr)
        {
            R=mid;
            dr=mid.len();
        }
        else
        {
            L=mid;
            dl=mid.len();
        }
        mid=vmid(L,R);
    }
    //cerr<<mid.len();
    return mid.len();
}
double d;
vec2 calcU(vec2 pt)
{
    double len=pt.len();
    double dis=d;
    double rlen=sqrt(pf(len)-pf(dis));
    vec2 upvec=pt+(-((pt.norm().Rrot(acos(dis/len)))*dis));
    return upvec;
}
vec2 calcD(vec2 pt)
{
    double len=pt.len();
    double dis=d;
    double rlen=sqrt(pf(len)-pf(dis));
    vec2 dwvec=pt.norm().Rrot(asin(dis/len))*rlen;
    return dwvec;
}
int n;
double XX0,YY0,t;
vector<point> pts;
vector<vec2> poly_vec;
vec2 strt;
int main()
{
    cin>>n>>XX0>>YY0>>d>>t;
    strt=vec2(XX0,YY0);
    for(int i=1;i<=n;++i)
    {
        double x,y;
        cin>>x>>y;
        pts.push_back(vec2(x,y));
    }
    for(int i=0;i<n;++i)
    {
        int nxt=(i+1)%n;
        vec2 lin=pts[nxt]+(-pts[i]);
        poly_vec.push_back(lin);
    }
    //check in poly
    double sgn=cross(poly_vec[0],pts[0])/abs(cross(poly_vec[0],pts[0]));
    bool flag=0,flag1=0;
    for(int i=1;i<n;++i)
    {
        double nsgn=cross(poly_vec[i],pts[i])/abs(cross(poly_vec[i],pts[i]));
        if(nsgn!=sgn)
        {
            flag=1;
            break;
        }
    }
    //check seg dist
    for(int i=0;i<n;++i)
    {
        int nxt=(i+1)%n;
        if(dis_seg(pts[i],pts[nxt])<=d)
        {
            flag1=1;
            break;
        }
    }
    //calc ang
    vec2 uvec=strt,dvec=strt;
    double angu=0,angd=1e18;
    for(int i=0;i<n;++i)
    {
        vec2 vecu=calcU(pts[i]),vecd=calcD(pts[i]);
        double uang=cross(strt.norm(),vecu.norm()),dang=cross(strt.norm(),vecd.norm());
        if(uang>angu)
        {
            uvec=vecu;
            angu=uang;
        }
        if(uang<angd)
        {
            dvec=vecu;
            angd=uang;
        }
        if(dang>angu)
        {
            uvec=vecd;
            angu=dang;
        }
        if(dang<angd)
        {
            dvec=vecd;
            angd=dang;
        }
    }
    if((!flag)||flag1)
    {
        //dot in circ
        //puts("1");
        printf("%.15lf\n",t);
    }
    else
    {
        double ans=0;
        double tm=t;
        if(angd>=0)
        {
            //no need to add and move
            double edang=asin(angu)-asin(angd);
            tm-=asin(angd);
            strt=dvec;
            if(tm>0)
            {
                while(tm>=2*PI)
                {
                    tm-=2*PI;
                    ans+=edang;
                }
                if(tm>edang)
                    ans+=edang;
                else
                    ans+=tm;
            }
        }
        else
        {
            //need to add and move
            if(angu<=0)
            {
                //all down
                tm-=asin(angd);
                if(tm>0)
                {
                    //remain time
                    strt=dvec;
                    double edang=asin(angu)-asin(angd);
                    while(tm>=2*PI)
                    {
                        tm-=2*PI;
                        ans+=edang;
                    }
                    if(tm>edang)
                        ans+=edang;
                    else
                        ans+=tm;
                }
            }
            else
            {
                //diff rot
                if(tm<asin(angu))
                    ans=tm;
                else
                {
                    ans=asin(angu);
                    tm-=asin(angd);
                    if(tm>0)
                    {
                        strt=dvec;
                        double edang=(2*PI)+asin(angu)-asin(angd);
                        while(tm>=2*PI)
                        {
                            tm-=2*PI;
                            ans+=edang;
                        }
                        if(tm>edang)
                            ans+=edang;
                        else
                            ans+=tm;
                    }
                }
            }
        }
        printf("%.15lf\n",ans);
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 4280kb

input:

3 1 0 1 1
1 2
2 1
2 2

output:

1.000000000000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 4276kb

input:

3 1 0 1 2
1 2
2 1
2 2

output:

1.570796326794897

result:

ok found '1.5707963', expected '1.5707963', error '0.0000000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 4208kb

input:

3 1 0 1 10000
1 2
2 1
2 2

output:

2500.707752257497759

result:

ok found '2500.7077523', expected '2500.7077523', error '0.0000000'

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 4148kb

input:

3 10000 10000 1 10000
10000 9999
10000 10000
9999 10000

output:

10000.384362016566229

result:

wrong answer 1st numbers differ - expected: '0.3842413', found: '10000.3843620', error = '10000.0001207'