QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#140281#4560. 定向越野myee100 ✓1984ms123764kbC++117.2kb2023-08-15 16:53:052023-08-15 16:53:07

Judging History

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

  • [2023-08-15 16:53:07]
  • 评测
  • 测评结果:100
  • 用时:1984ms
  • 内存:123764kb
  • [2023-08-15 16:53:05]
  • 提交

answer

// 那就是希望。
// 即便需要取模,也是光明。

#include <algorithm>
#include <queue>
#include <math.h>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
    T ans=1%mod;
    while(index)
    {
        if(index&1)ans=ans*base%mod;
        base=base*base%mod,index>>=1;
    }
    return ans;
}
namespace Geo2D
{
    const dbl Pi=acosl(-1);
    const dbl eps=1e-9;
    struct Dbl
    {
        dbl v;
        Dbl():v(0){}
        Dbl(dbl v):v(v){}
        dbl&operator()(){return v;}
        voi read(){scanf("%lf",&v);}
        friend Dbl operator+(Dbl a){return a;}
        friend Dbl operator+(Dbl a,Dbl b){return a()+b();}
        friend Dbl operator-(Dbl a){return-a();}
        friend Dbl operator-(Dbl a,Dbl b){return a()-b();}
        friend Dbl operator*(Dbl a,Dbl b){return a()*b();}
        friend Dbl operator/(Dbl a,Dbl b){return a()/b();}
        friend bol operator<(Dbl a,Dbl b){return a()+eps<b();}
        friend bol operator>(Dbl a,Dbl b){return a()>b()+eps;}
        friend bol operator<=(Dbl a,Dbl b){return a()<b()+eps;}
        friend bol operator>=(Dbl a,Dbl b){return a()+eps>b();}
        friend bol operator==(Dbl a,Dbl b){return a()<b()+eps&&a()+eps>b();}
        friend bol operator!=(Dbl a,Dbl b){return a()>b()+eps||a()+eps<b();}
        Dbl _sin(){return sin(v);}
        Dbl _cos(){return cos(v);}
        Dbl _acos(){
            if(*this==1)return 0;
            if(*this==-1)return Pi;
            return acos(v);
        }
        Dbl _sqrt(){return sqrt(v);}
    };
    struct Vec
    {
        Dbl x,y;
        Vec():x(),y(){}
        Vec(Dbl x,Dbl y):x(x),y(y){}
        friend Vec operator+(Vec a,Vec b){return{a.x+b.x,a.y+b.y};}
        friend Vec operator-(Vec a,Vec b){return{a.x-b.x,a.y-b.y};}
        friend Vec operator*(Dbl a,Vec b){return{a*b.x,a*b.y};}
        friend Vec operator*(Vec a,Dbl b){return{a.x*b,a.y*b};}
        friend Dbl operator*(Vec a,Vec b){return a.x*b.x+a.y*b.y;}
        friend Dbl operator^(Vec a,Vec b){return a.x*b.y-a.y*b.x;}
        friend Vec operator/(Vec a,Dbl b){return{a.x/b,a.y/b};}
        friend bol operator==(Vec a,Vec b){return a.x==b.x&&a.y==b.y;}
        Vec&operator+=(Vec b){return*this=*this+b;}
        Vec&operator-=(Vec b){return*this=*this-b;}
        Dbl len_sqr(){return*this**this;}
        Dbl len(){return len_sqr()._sqrt();}
        friend Dbl dist_sqr(Vec a,Vec b){return(a-b).len_sqr();}
        friend Dbl dist(Vec a,Vec b){return(a-b).len();}
        voi read(){x.read(),y.read();}
        Vec rotate(Dbl c,Dbl s){return{c*x-s*y,s*x+c*y};}
        Vec rotate(Dbl angle){return rotate(angle._cos(),angle._sin());}
        int state()
        {
            if(x>0&&y==0)return 1;
            if(x>0&&y>0)return 2;
            if(x==0&&y>0)return 3;
            if(x<0&&y>0)return 4;
            if(x<0&&y==0)return 5;
            if(x<0&&y<0)return 6;
            if(x==0&&y<0)return 7;
            if(x>0&&y<0)return 8;
            return 0;
        }
    };
    bol cmp_atan2(Vec a,Vec b){
        if(a.state()!=b.state())return a.state()<b.state();
        return(a^b)>0;
    }
    typedef std::vector<Vec>Vecs;
    typedef Vec Point;
    typedef Vecs Points;
}
// Heaven and Earth... My guiding star...
// Akira Complex R.I.P.
using namespace Geo2D;
Point O[505],P[1000005];Dbl R[505],Dist[1000005];bol G[1000005];uint tp;
std::vector<uint>V[505];std::vector<std::pair<uint,Dbl> >Way[1000005];
int main()
{
#ifdef MYEE
    freopen("QAQ.in","r",stdin);
    freopen("QAQ.out","w",stdout);
#endif
    P[0].read(),P[1].read(),tp=2;
    uint n=0,m;scanf("%u",&m);while(m--)O[n].read(),R[n].read(),n+=R[n]!=0;
    auto check=[&](Point p,Point q)
    {
        if(p==q)return true;
        Vec f=q-p;Vec g=f/f.len_sqr();Dbl r;
        for(uint k=0;k<n;k++)if((r=g*(O[k]-p))>0&&r<1&&(p-O[k]+r*f).len()<R[k])return false;
        return true;
    };
    if(check(P[0],P[1]))Way[0].push_back({1,dist(P[0],P[1])}),Way[1].push_back({0,dist(P[0],P[1])});
    for(uint o=0;o<2;o++)for(uint i=0;i<n;i++)
    {
        Dbl d=dist(O[i],P[o]);Dbl c=R[i]/d;Dbl s=(1-c*c)._sqrt();Point p;
        p=O[i]+((P[o]-O[i])/d*R[i]).rotate(c,s);
        if(check(P[o],p))V[i].push_back(tp),
            Way[o].push_back({tp,dist(p,P[o])}),Way[tp].push_back({o,dist(p,P[o])}),P[tp++]=p;
        p=O[i]+((P[o]-O[i])/d*R[i]).rotate(c,-s);
        if(check(P[o],p))V[i].push_back(tp),
            Way[o].push_back({tp,dist(p,P[o])}),Way[tp].push_back({o,dist(p,P[o])}),P[tp++]=p;
    }
    for(uint i=0;i<n;i++)for(uint j=i+1;j<n;j++)
    {
        Dbl d=dist(O[i],O[j]),c,s;Point p,q;
        c=(R[i]+R[j])/d,s=(1-c*c)._sqrt();
        p=O[i]+((O[j]-O[i])/d*R[i]).rotate(c,s),q=O[j]+((O[i]-O[j])/d*R[j]).rotate(c,s);
        if(check(p,q))V[i].push_back(tp),V[j].push_back(tp+1),
            Way[tp].push_back({tp+1,dist(p,q)}),Way[tp+1].push_back({tp,dist(p,q)}),P[tp++]=p,P[tp++]=q;
        p=O[i]+((O[j]-O[i])/d*R[i]).rotate(c,-s),q=O[j]+((O[i]-O[j])/d*R[j]).rotate(c,-s);
        if(check(p,q))V[i].push_back(tp),V[j].push_back(tp+1),
            Way[tp].push_back({tp+1,dist(p,q)}),Way[tp+1].push_back({tp,dist(p,q)}),P[tp++]=p,P[tp++]=q;
        c=(R[i]-R[j])/d,s=(1-c*c)._sqrt();
        p=O[i]+((O[j]-O[i])/d*R[i]).rotate(c,s),q=O[j]+((O[i]-O[j])/d*R[j]).rotate(-c,-s);
        if(check(p,q))V[i].push_back(tp),V[j].push_back(tp+1),
            Way[tp].push_back({tp+1,dist(p,q)}),Way[tp+1].push_back({tp,dist(p,q)}),P[tp++]=p,P[tp++]=q;
        p=O[i]+((O[j]-O[i])/d*R[i]).rotate(c,-s),q=O[j]+((O[i]-O[j])/d*R[j]).rotate(-c,s);
        if(check(p,q))V[i].push_back(tp),V[j].push_back(tp+1),
            Way[tp].push_back({tp+1,dist(p,q)}),Way[tp+1].push_back({tp,dist(p,q)}),P[tp++]=p,P[tp++]=q;
    }
    for(uint i=0;i<n;i++)
    {
        std::sort(V[i].begin(),V[i].end(),[&](uint a,uint b){return cmp_atan2(P[a]-O[i],P[b]-O[i]);});
        for(uint j=0,a=V[i].back(),b;j<V[i].size();a=b,j++)
        {
            b=V[i][j];
            Dbl d=((P[a]-O[i])*(P[b]-O[i])/(R[i]*R[i]))._acos()*R[i];
            Way[a].push_back({b,d}),Way[b].push_back({a,d});
        }
    }
    for(uint i=1;i<tp;i++)Dist[i]=2e5;
    std::priority_queue<std::pair<Dbl,uint>,std::vector<std::pair<Dbl,uint> >,std::greater<std::pair<Dbl,uint> > >Q;
    Q.push({0,0});
    while(Q.size())
    {
        uint p=Q.top().second;Q.pop();if(G[p])continue;
        G[p]=1;for(auto s:Way[p])if(_min(Dist[s.first],Dist[p]+s.second))Q.push({Dist[s.first],s.first});
    }
    printf("%.1lf\n",Dist[1]());
    return 0;
}

// 那就是希望。
// 即便需要取模,也是光明。

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 5
Accepted
time: 3ms
memory: 51088kb

input:

-100 27 98 2
0

output:

199.6

result:

ok single line: '199.6'

Test #2:

score: 5
Accepted
time: 5ms
memory: 51400kb

input:

-136 25 171 -3
1
0 0 100

output:

361.1

result:

ok single line: '361.1'

Test #3:

score: 5
Accepted
time: 5ms
memory: 51388kb

input:

-100 0 100 0
1
10 0 10

output:

201.0

result:

ok single line: '201.0'

Test #4:

score: 5
Accepted
time: 3ms
memory: 51228kb

input:

-136 25 174 -4
2
-50 50 60
70 -20 61

output:

340.0

result:

ok single line: '340.0'

Test #5:

score: 5
Accepted
time: 3ms
memory: 51188kb

input:

-136 25 171 -3
2
-50 50 60
80 50 60

output:

314.8

result:

ok single line: '314.8'

Test #6:

score: 5
Accepted
time: 7ms
memory: 51316kb

input:

-136 25 171 -3
3
-50 50 60
10 -20 20
80 50 60

output:

316.5

result:

ok single line: '316.5'

Test #7:

score: 5
Accepted
time: 4ms
memory: 51292kb

input:

-50 90 249 103
4
0 0 100
200 0 100
0 200 100
200 200 100

output:

300.3

result:

ok single line: '300.3'

Test #8:

score: 5
Accepted
time: 6ms
memory: 51584kb

input:

872 -756 -352 288
5
826 775 313
914 429 44
975 357 50
12 920 513
260 -234 667

output:

2203.4

result:

ok single line: '2203.4'

Test #9:

score: 5
Accepted
time: 8ms
memory: 51416kb

input:

-936 602 -345 -983
8
604 180 341
-496 117 166
424 -650 366
531 863 345
-831 133 169
-800 503 167
-127 6 219
-641 -191 174

output:

1775.3

result:

ok single line: '1775.3'

Test #10:

score: 5
Accepted
time: 1ms
memory: 51372kb

input:

-173 -249 -171 -221
16
-225 -309 18
-225 -273 18
-225 -237 18
-225 -201 18
-189 -309 18
-189 -273 18
-189 -237 18
-189 -201 18
-153 -309 18
-153 -273 18
-153 -237 18
-153 -201 18
-117 -309 18
-117 -273 18
-117 -237 18
-117 -201 18

output:

28.2

result:

ok single line: '28.2'

Test #11:

score: 5
Accepted
time: 5ms
memory: 51580kb

input:

985 552 -332 -758
20
329 229 213
926 318 203
-891 -472 129
-41 687 287
-646 692 286
-327 -993 78
-476 -985 71
151 -548 167
-864 -729 129
-406 -59 192
269 -725 27
306 -676 34
-428 -423 37
-32 -835 53
675 -1 202
-61 -961 76
-321 308 184
-350 -438 42
363 -288 89
326 -103 99

output:

1898.6

result:

ok single line: '1898.6'

Test #12:

score: 5
Accepted
time: 6ms
memory: 52164kb

input:

-499 -717 239 -53
50
-817 341 21
21 637 21
398 979 21
-29 -169 21
353 602 21
-758 -744 21
-391 -668 21
217 74 21
-511 54 21
33 15 21
-252 -837 21
-822 863 21
-818 -576 21
978 814 21
934 864 21
-968 -526 21
-998 -79 21
-745 -379 21
491 -161 21
-874 -618 21
-693 -680 21
800 629 21
-140 249 21
223 463 ...

output:

994.2

result:

ok single line: '994.2'

Test #13:

score: 5
Accepted
time: 12ms
memory: 52000kb

input:

-161 -739 -162 -587
100
-251 -761 18
-251 -725 18
-251 -689 18
-251 -653 18
-251 -617 18
-251 -581 18
-251 -545 18
-251 -509 18
-251 -473 18
-251 -437 18
-215 -761 18
-215 -725 18
-215 -689 18
-215 -653 18
-215 -617 18
-215 -581 18
-215 -545 18
-215 -509 18
-215 -473 18
-215 -437 18
-179 -761 18
-17...

output:

152.0

result:

ok single line: '152.0'

Test #14:

score: 5
Accepted
time: 39ms
memory: 52304kb

input:

826 450 -306 925
200
108 673 32
506 283 36
-764 -151 10
830 678 45
-918 -16 98
-25 479 19
299 -70 10
33 787 24
-808 181 35
-446 -32 21
-574 -690 12
835 -921 96
-555 -510 14
-14 515 18
52 -362 7
567 -424 2
-364 -55 48
357 112 84
461 -134 14
340 -717 104
63 -59 7
525 -298 37
289 2 38
-587 167 37
640 -...

output:

1232.9

result:

ok single line: '1232.9'

Test #15:

score: 5
Accepted
time: 154ms
memory: 56980kb

input:

-38 -199 -39 -284
400
-271 -515 18
-271 -479 18
-271 -443 18
-271 -407 18
-271 -371 18
-271 -335 18
-271 -299 18
-271 -263 18
-271 -227 18
-271 -191 18
-271 -155 18
-271 -119 18
-271 -83 18
-271 -47 18
-271 -11 18
-271 25 18
-271 61 18
-271 97 18
-271 133 18
-271 169 18
-235 -515 18
-235 -479 18
-23...

output:

85.1

result:

ok single line: '85.1'

Test #16:

score: 5
Accepted
time: 155ms
memory: 56996kb

input:

166 281 -195 642
400
-281 8 18
-281 44 18
-281 80 18
-281 116 18
-281 152 18
-281 188 18
-281 224 18
-281 260 18
-281 296 18
-281 332 18
-281 368 18
-281 404 18
-281 440 18
-281 476 18
-281 512 18
-281 548 18
-281 584 18
-281 620 18
-281 656 18
-281 692 18
-245 8 18
-245 44 18
-245 80 18
-245 116 18...

output:

574.9

result:

ok single line: '574.9'

Test #17:

score: 5
Accepted
time: 1984ms
memory: 123764kb

input:

776 -462 -166 326
500
-584 400 1
-312 68 1
-235 -138 1
522 100 1
76 701 1
-763 674 1
-873 -149 1
-82 -480 1
560 -945 1
-727 -607 1
-174 619 1
-680 752 1
831 693 1
595 131 1
161 271 1
-984 592 1
70 821 1
-667 -786 1
423 -185 1
148 -769 1
-760 7 1
-872 -388 1
806 -139 1
934 -590 1
668 521 1
22 411 1
1...

output:

1228.1

result:

ok single line: '1228.1'

Test #18:

score: 5
Accepted
time: 1947ms
memory: 122508kb

input:

933 -324 -919 985
500
-357 -466 1
454 150 1
877 -436 1
704 -838 1
-68 -533 1
743 -733 1
466 613 1
-492 -570 1
-675 -456 1
-316 171 1
-558 64 1
-504 517 1
-725 79 1
777 538 1
-622 -808 1
893 6 1
280 225 1
39 -493 1
217 421 1
-405 71 1
-209 888 1
-304 -97 1
-772 740 1
-309 -822 1
487 -558 1
988 214 1
...

output:

2267.9

result:

ok single line: '2267.9'

Test #19:

score: 5
Accepted
time: 336ms
memory: 53656kb

input:

498 -626 -706 659
500
750 -390 84
-680 797 22
224 -477 45
-276 157 12
825 -215 35
889 365 23
-331 141 41
50 -395 28
710 952 14
857 -605 17
-639 -599 4
645 844 15
-133 963 49
423 434 17
147 631 5
782 359 7
881 782 12
-682 -622 35
-290 347 7
936 -943 5
-986 127 11
301 -17 13
140 957 29
-635 662 42
236...

output:

1785.5

result:

ok single line: '1785.5'

Test #20:

score: 5
Accepted
time: 324ms
memory: 53600kb

input:

622 -445 -234 14
500
618 -568 22
-186 -295 48
777 -658 10
-747 50 20
-731 -783 32
-858 372 10
-395 -690 2
-292 243 7
-590 570 18
-682 550 20
-636 -741 44
901 -668 24
143 196 64
-67 -541 74
607 -986 5
609 -467 24
-670 -684 22
202 -363 28
-827 870 19
440 202 12
-79 209 11
-308 -967 69
374 -42 15
661 4...

output:

974.0

result:

ok single line: '974.0'

Extra Test:

score: 0
Extra Test Passed