QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#773171#9576. Ordainer of Inexorable JudgmentArnold_6WA 0ms4216kbC++178.2kb2024-11-23 02:50:212024-11-23 02:50:21

Judging History

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

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

answer

#include <bits/stdc++.h>
using namespace std;
#define db long double

// using point_t=long long;
using point_t=long double;  //全局数据类型

constexpr point_t eps=1e-12;
constexpr point_t INF=numeric_limits<point_t>::max();
constexpr long double PI=3.1415926535897932384l;

// 点与向量
template<typename T> struct point
{
    T x,y;

    bool operator==(const point &a) const {return (abs(x-a.x)<=eps && abs(y-a.y)<=eps);}
    bool operator<(const point &a) const {if (abs(x-a.x)<=eps) return y<a.y-eps; return x<a.x-eps;}
    bool operator>(const point &a) const {return !(*this<a || *this==a);}
    point operator+(const point &a) const {return {x+a.x,y+a.y};}
    point operator-(const point &a) const {return {x-a.x,y-a.y};}
    point operator-() const {return {-x,-y};}
    point operator*(const T k) const {return {k*x,k*y};}
    point operator/(const T k) const {return {x/k,y/k};}
    T operator*(const point &a) const {return x*a.x+y*a.y;}  // 点积
    T operator^(const point &a) const {return x*a.y-y*a.x;}  // 叉积,注意优先级
    int toleft(const point &a) const {const auto t=(*this)^a; return (t>eps)-(t<-eps);}  // to-left 测试
    T len2() const {return (*this)*(*this);}  // 向量长度的平方
    T dis2(const point &a) const {return (a-(*this)).len2();}  // 两点距离的平方

    // 涉及浮点数
    long double len() const {return sqrtl(len2());}  // 向量长度
    long double dis(const point &a) const {return sqrtl(dis2(a));}  // 两点距离
    long double ang(const point &a) const {return acosl(max(-1.0l,min(1.0l,((*this)*a)/(len()*a.len()))));}  // 向量夹角
    point rot(const long double rad) const {return {x*cos(rad)-y*sin(rad),x*sin(rad)+y*cos(rad)};}  // 逆时针旋转(给定角度)
    point rot(const long double cosr,const long double sinr) const {return {x*cosr-y*sinr,x*sinr+y*cosr};}  // 逆时针旋转(给定角度的正弦与余弦)
};

using Point=point<point_t>;

// 极角排序
struct argcmp
{
    bool operator()(const Point &a,const Point &b) const
    {
        // const auto quad=[](const Point &a)
        // {
        //     if (a.y<-eps) return 1;
        //     if (a.y>eps) return 4;
        //     if (a.x<-eps) return 5;
        //     if (a.x>eps) return 3;
        //     return 2;
        // };
        // const int qa=quad(a),qb=quad(b);
        // if (qa!=qb) return qa<qb;
        const auto t=a^b;
        // if (abs(t)<=eps) return a*a<b*b-eps;  // 不同长度的向量需要分开
        return t>eps;
    }
};


// 直线
template<typename T> struct line
{
    point<T> p,v;  // p 为直线上一点,v 为方向向量

    bool operator==(const line &a) const {return v.toleft(a.v)==0 && v.toleft(p-a.p)==0;}
    int toleft(const point<T> &a) const {return v.toleft(a-p);}  // to-left 测试
    bool operator<(const line &a) const  // 半平面交算法定义的排序
    {
        if (abs(v^a.v)<=eps && v*a.v>=-eps) return toleft(a.p)==-1;
        return argcmp()(v,a.v);
    }

    // 涉及浮点数
    point<T> inter(const line &a) const {return p+v*((a.v^(p-a.p))/(v^a.v));}  // 直线交点
    long double dis(const point<T> &a) const {return abs(v^(a-p))/v.len();}  // 点到直线距离
    point<T> proj(const point<T> &a) const {return p+v*((v*(a-p))/(v*v));}  // 点在直线上的投影
};

using Line=line<point_t>;

//线段
template<typename T> struct segment
{
    point<T> a,b;

    bool operator<(const segment &s) const {return make_pair(a,b)<make_pair(s.a,s.b);}

    // 判定性函数建议在整数域使用

    // 判断点是否在线段上
    // -1 点在线段端点 | 0 点不在线段上 | 1 点严格在线段上
    int is_on(const point<T> &p) const  
    {
        if (p==a || p==b) return -1;
        return (p-a).toleft(p-b)==0 && (p-a)*(p-b)<-eps;
    }

    // 判断线段直线是否相交
    // -1 直线经过线段端点 | 0 线段和直线不相交 | 1 线段和直线严格相交
    int is_inter(const line<T> &l) const
    {
        if (l.toleft(a)==0 || l.toleft(b)==0) return -1;
        return l.toleft(a)!=l.toleft(b);
    }
    
    // 判断两线段是否相交
    // -1 在某一线段端点处相交 | 0 两线段不相交 | 1 两线段严格相交
    int is_inter(const segment<T> &s) const
    {
        if (is_on(s.a) || is_on(s.b) || s.is_on(a) || s.is_on(b)) return -1;
        const line<T> l{a,b-a},ls{s.a,s.b-s.a};
        return l.toleft(s.a)*l.toleft(s.b)==-1 && ls.toleft(a)*ls.toleft(b)==-1;
    }

    // 点到线段距离
    long double dis(const point<T> &p) const
    {
        if ((p-a)*(b-a)<-eps || (p-b)*(a-b)<-eps) return min(p.dis(a),p.dis(b));
        const line<T> l{a,b-a};
        return l.dis(p);
    }

    // 两线段间距离
    long double dis(const segment<T> &s) const
    {
        if (is_inter(s)) return 0;
        return min({dis(s.a),dis(s.b),s.dis(a),s.dis(b)});
    }
};

using Segment=segment<point_t>;

// 多边形
template<typename T> struct polygon
{
    vector<point<T>> p;  // 以逆时针顺序存储

    size_t nxt(const size_t i) const {return i==p.size()-1?0:i+1;}
    size_t pre(const size_t i) const {return i==0?p.size()-1:i-1;}

};

using Polygon=polygon<point_t>;

//凸多边形
template<typename T> struct convex: polygon<T>
{};

using Convex=convex<point_t>;

// 圆
struct Circle
{
    Point c;
    long double r;

    bool operator==(const Circle &a) const {return c==a.c && abs(r-a.r)<=eps;}
    long double circ() const {return 2*PI*r;}  // 周长
    long double area() const {return PI*r*r;}  // 面积

    // 过圆外一点圆的切线
    vector<Line> tangent(const Point &a) const
    {
        Point e=a-c; e=e/e.len()*r;
        const long double costh=r/c.dis(a),sinth=sqrt(1-costh*costh);
        const Point t1=c+e.rot(costh,-sinth),t2=c+e.rot(costh,sinth);
        return vector<Line>{{a,t1-a},{a,t2-a}};
    }

};

int main()
{
    // Point a{1.0,0},b{-1.0,sqrt(3)};cout<<a.ang(b)<<endl;

    int n;
    db x0,y0,d,t;
    cin>>n>>x0>>y0>>d>>t;
    Point st={x0,y0};
    Polygon poly;
    Circle c{{0.0,0.0},d};
    for(int i=1;i<=n;i++)
    {
        db x,y;
        cin>>x>>y;
        poly.p.push_back({x,y});
    }

    Polygon pp;
    for(auto p:poly.p)
    {
        vector<Line> tmp=c.tangent(p);
        Point v1=-tmp[0].v,v2=-tmp[1].v;

        pp.p.push_back(v1);
        pp.p.push_back(v2);
    }

    sort(pp.p.begin(),pp.p.end(),argcmp());

    // for(auto i:pp.p)
    // {
    //     cout<<i.x<<" "<<i.y<<endl;
    // }

    db tt=pp.p[0].ang(pp.p[pp.p.size()-1]);
    // cout<<tt<<endl;

    Point p1=pp.p[0],p2=pp.p[pp.p.size()-1];

    // if((p1^p2)<0)swap(p1,p2);

    db ans=0;

    int times=0;

    if(t-2*PI>=eps)
    {
        times=t/2.0/PI;
        ans=times*tt;
        t=t-2.0*PI*times;
    }

    if(t<=eps)
    {
        cout<<ans;
        return 0;
    }

    // cout<<times<<" "<<fixed<<setprecision(15)<<t<<" "<<ans<<endl<<endl;
    
    Point ed=st.rot(t);
    // cout<<ed.x<<" "<<ed.y<<endl;
    // cout<<p1.x<<" "<<p1.y<<endl;
    // cout<<p2.x<<" "<<p2.y<<endl;
    // cout<<p1.toleft(ed)<<" "<<p2.toleft(ed)<<endl;
    if((p1.toleft(st))>=0 && (p2.toleft(st))<0 )
    {
        // cout<<"------";
        if(st.toleft(ed)>=0)
        {
            if((p1.toleft(ed))>=0 && (p2.toleft(ed))<=0)
            {
                ans+=st.ang(ed);
            }
            else 
            {
                ans+=st.ang(p2);
            }
        }
        else
        {
            if((p1.toleft(ed))>=0 && (p2.toleft(ed))<=0)
            {
                ans+=st.ang(p2)+p1.ang(ed);
            }
            else 
            {
                ans+=st.ang(p2);
            }
        }
        
    }
    else
    {
        if((p1.toleft(ed))>=0 && (p2.toleft(ed))<=0)
        {
            ans+=p1.ang(ed);
        }
        else
        {
            db ang=st.ang(ed);
            if(st.toleft(ed)<0 || fabs(st*ed+1)<=eps)
            {
                ang=2*PI-ang;
            }

            // cout<<"ang="<<ang<<endl;
            if(ang-tt>=eps)ans+=tt;
        }
    }
    
    cout<<fixed<<setprecision(15)<<ans;

    
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 4140kb

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: 4204kb

input:

3 1 0 1 10000
1 2
2 1
2 2

output:

2500.707752257475418

result:

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

Test #4:

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

input:

3 10000 10000 1 10000
10000 9999
10000 10000
9999 10000

output:

0.384241300289928

result:

ok found '0.3842413', expected '0.3842413', error '0.0000000'

Test #5:

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

input:

3 -10000 -10000 10000 10000
-10000 -9999
-10000 -10000
-9999 -10000

output:

2500.240670009608470

result:

ok found '2500.2406700', expected '2500.2406700', error '0.0000000'

Test #6:

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

input:

4 1 0 1 10000
-2 3400
-4 10000
-4 -10000
-2 -3400

output:

4999.219115408742558

result:

ok found '4999.2191154', expected '4999.2191154', error '0.0000000'

Test #7:

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

input:

4 1 0 1 10000
-2 3300
-4 10000
-4 -10000
-2 -3300

output:

4999.200391854814572

result:

ok found '4999.2003919', expected '4999.2003919', error '0.0000000'

Test #8:

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

input:

4 -3040 2716 2147 2
-9033 -8520
-8999 -8533
-8988 -8511
-9004 -8495

output:

0.350830058342073

result:

ok found '0.3508301', expected '0.3508301', error '0.0000000'

Test #9:

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

input:

3 8168 -766 1549 1256
-3951 -6425
-3874 -6439
-3911 -6389

output:

84.832861161006953

result:

ok found '84.8328612', expected '84.8328612', error '0.0000000'

Test #10:

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

input:

8 2977 -3175 8766 2
-4868 7759
-4867 7925
-4867 7950
-4886 7952
-4979 7953
-5048 7877
-5003 7761
-4936 7759

output:

0.327860646906109

result:

ok found '0.3278606', expected '0.3278606', error '0.0000000'

Test #11:

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

input:

13 -1715 -4640 267 8651
272 6659
264 6660
208 6664
108 6625
107 6621
93 6564
90 6551
90 6485
124 6474
219 6477
283 6525
288 6591
286 6657

output:

153.589622784682281

result:

ok found '153.5896228', expected '153.5896228', error '0.0000000'

Test #12:

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

input:

8 -9743 -7629 775 7
-194 981
-191 1720
-193 1845
-705 1929
-959 1950
-1131 1894
-1151 1604
-1031 1020

output:

2.046006204355634

result:

ok found '2.0460062', expected '2.0460062', error '0.0000000'

Test #13:

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

input:

9 -6770 -1426 3491 1918
-2118 2886
-2063 3245
-2122 3709
-2129 3737
-2850 3718
-2984 3650
-3042 3462
-3028 2972
-2688 2888

output:

822.241184963714826

result:

ok found '822.2411850', expected '822.2411850', error '0.0000000'

Test #14:

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

input:

12 1616 -7384 5256 10
-5607 2623
-5838 2843
-6117 2986
-6592 3169
-7129 3120
-7334 3069
-7406 2295
-7369 1712
-7091 1287
-6312 1252
-5596 1592
-5457 2088

output:

3.038765377139072

result:

ok found '3.0387654', expected '3.0387654', error '0.0000000'

Test #15:

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

input:

10 -4546 5056 639 2996
4851 -3506
6078 -3725
6629 -3674
6775 -3296
6743 -2137
6585 -1866
5334 -1837
4950 -2020
4873 -2260
4852 -3240

output:

262.423969078937369

result:

ok found '262.4239691', expected '262.4239691', error '0.0000000'

Test #16:

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

input:

20 4847 -6818 2502 2
-2164 -3844
-2453 -3826
-4654 -3818
-5073 -3829
-5212 -3833
-5828 -3921
-5889 -6065
-5896 -6716
-5877 -7349
-5855 -7457
-5619 -7711
-5485 -7786
-3743 -7809
-2345 -7747
-2075 -7682
-1960 -7364
-1900 -7015
-1901 -6391
-1922 -4091
-1968 -4028

output:

1.490164589595378

result:

wrong answer 1st numbers differ - expected: '0.0000000', found: '1.4901646', error = '1.4901646'