QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#797868#9861. Mountain Is Quiet and AlonequailtyAC ✓48ms4404kbC++232.4kb2024-12-03 20:02:322024-12-03 20:02:32

Judging History

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

  • [2024-12-03 20:02:32]
  • 评测
  • 测评结果:AC
  • 用时:48ms
  • 内存:4404kb
  • [2024-12-03 20:02:32]
  • 提交

answer

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

const int MAXN=1005;
const db PI=acos(-1.0);
const db eps=1e-8;

inline int sgn(db x)
{
    if(x>eps)return 1;
    if(x<-eps)return -1;
    return 0;
}

struct Point
{
    db x,y;
    explicit Point(db _x=0,db _y=0):x(_x),y(_y){}
    Point operator + (const Point &t)const { return Point(x+t.x,y+t.y); }
    Point operator - (const Point &t)const { return Point(x-t.x,y-t.y); }
    Point operator * (db t)const { return Point(x*t,y*t); }
    db operator * (const Point &t)const { return x*t.y-y*t.x; }
    db operator ^ (const Point &t)const { return x*t.x+y*t.y; }
    db ang(const Point& t)const {
        db r=atan2((*this)*t,(*this)^t);
        return (r<0 ? r+2*PI : r);
    };
    Point rot(db ang)const { return Point(x*cos(ang)-y*sin(ang),x*sin(ang)+y*cos(ang)); }
    db len()const { return sqrt(x*x+y*y); }
}p[MAXN];

int main()
{
    int n;
    scanf("%d",&n),n++;
    p[0]=Point(-2,0),p[1]=Point(0,0);
    for(int i=2;i<=n;i++)
        scanf("%Lf%Lf",&p[i].x,&p[i].y);
    Point head=p[n]+Point(0,1),tail=p[n],center=p[n];
    bool head_up=1;
    db res=0;
    while(sgn(head.y)>0)
    {
        Point hit=(head_up ? head : tail);
        Point t_center;
        bool t_head_up=0;
        db ang=2*PI,len=(hit-center).len();
        for(int i=0;i<=n;i++)
        {
            if(sgn(p[i].x-center.x)>=0)break;
            if(sgn((p[i]-center).len()-len)>0)continue;
            db tmp=(hit-center).ang(p[i]-center);
            if(tmp<ang)ang=tmp,t_center=p[i],t_head_up=head_up;
        }
        for(int i=0;i<n;i++)
        {
            Point s=p[i],e=(sgn(p[i+1].x-center.x)>0 ? center : p[i+1]);
            if(sgn((s-center).len()-len)<0 || sgn((e-center).len()-len)>0)continue;
            db l=0,r=1;
            for(int _=0;_<50;_++)
            {
                db m=(l+r)/2;
                Point t=(s-e)*m+e;
                if((t-center).len()>len)r=m;
                else l=m;
            }
            Point t_hit=(s-e)*((l+r)/2)+e;
            db tmp=(hit-center).ang(t_hit-center);
            if(tmp<ang)ang=tmp,t_center=t_hit,t_head_up=!head_up;
            break;
        }
        res+=(head-center).len()*ang;
        head=center+(head-center).rot(ang);
        tail=center+(tail-center).rot(ang);
        center=t_center;
        head_up=t_head_up;
    }
    return 0*printf("%.12Lf\n",res);
}

详细

Test #1:

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

input:

1
0.5 0.5

output:

2.094395102393

result:

ok found '2.0943951', expected '2.0943951', error '0.0000000'

Test #2:

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

input:

2
0.2 0.8
1 1

output:

4.465554239614

result:

ok found '4.4655542', expected '4.4655542', error '0.0000000'

Test #3:

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

input:

1
0.324986 0.892093

output:

2.672752573206

result:

ok found '2.6727526', expected '2.6727526', error '0.0000000'

Test #4:

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

input:

19
0.031812 0.242618
0.461687 1.077180
0.845461 1.930323
1.665843 2.382021
1.688456 2.568847
2.048141 3.412179
2.144824 3.877603
2.515724 4.389138
2.648840 4.902697
3.231260 5.358572
4.161254 6.227717
4.314110 6.838521
6.463958 12.760608
6.868936 12.814426
7.797235 13.203219
8.736304 14.029216
13.88...

output:

51.082115702812

result:

ok found '51.0821157', expected '51.0821157', error '0.0000000'

Test #5:

score: 0
Accepted
time: 1ms
memory: 4236kb

input:

34
1.019270 4.993572
2.006790 5.394932
2.982753 5.550769
3.034861 6.261258
3.427933 6.273919
4.006458 7.209462
4.920711 7.483791
8.820786 11.675906
12.307634 12.554809
12.425134 13.023063
13.221761 13.159334
13.283453 13.345257
14.157556 14.036401
17.848403 19.768013
18.550931 19.972571
18.897052 20...

output:

76.644775835389

result:

ok found '76.6447758', expected '76.6447758', error '0.0000000'

Test #6:

score: 0
Accepted
time: 1ms
memory: 4328kb

input:

65
0.069962 0.313028
0.346500 0.488716
1.338325 0.540418
2.019196 0.803382
2.593272 1.734267
7.419697 7.123181
7.723916 7.692761
8.398378 7.874394
8.524276 8.124536
8.947395 8.950169
9.817547 8.986039
10.177135 9.734688
10.296691 10.005594
10.548511 10.679687
10.624483 11.404340
10.931958 11.510819
...

output:

118.143842178669

result:

ok found '118.1438422', expected '118.1438422', error '0.0000000'

Test #7:

score: 0
Accepted
time: 1ms
memory: 4328kb

input:

79
0.078044 0.010051
0.498227 0.605682
0.775662 1.429392
0.844835 2.270136
1.104792 3.254016
1.490100 3.980076
1.571207 4.770968
2.130444 5.662572
2.284015 6.542677
3.200349 7.482048
3.350384 8.045320
3.813510 8.356687
4.783541 9.154609
5.580154 10.115621
5.833360 10.461472
6.419648 12.055267
7.0891...

output:

117.964669996827

result:

ok found '117.9646700', expected '117.9646700', error '0.0000000'

Test #8:

score: 0
Accepted
time: 1ms
memory: 4224kb

input:

97
0.844074 0.860929
1.195193 1.284053
1.779170 2.263398
2.457985 2.752469
3.417428 3.682635
4.082844 3.741900
4.356155 3.898396
4.916590 4.249950
10.855796 6.958835
11.262006 7.617787
12.203583 7.773207
12.725713 8.256758
13.279372 8.635637
17.242408 9.069582
17.818234 9.196889
18.019740 9.498454
1...

output:

205.924300859672

result:

ok found '205.9243009', expected '205.9243009', error '0.0000000'

Test #9:

score: 0
Accepted
time: 2ms
memory: 4340kb

input:

172
0.696609 0.728065
0.729195 1.320783
1.104997 1.447759
1.131185 2.205405
1.806330 2.441318
2.702839 2.711574
3.132256 3.590006
3.726537 4.501013
4.580531 5.219632
5.165177 5.319764
5.434842 6.319712
5.903592 6.626663
6.821509 6.628313
8.888411 7.289256
9.727665 7.712548
10.042004 8.284472
10.5071...

output:

309.857104898583

result:

ok found '309.8571049', expected '309.8571049', error '0.0000000'

Test #10:

score: 0
Accepted
time: 3ms
memory: 4328kb

input:

233
0.875178 0.488561
1.486129 1.451795
7.363462 4.017530
12.165040 9.180203
12.216451 9.915291
12.850695 10.398489
12.972177 11.384951
13.449863 11.626896
14.297810 11.986842
14.323017 12.399251
14.869487 12.892458
14.905442 13.303785
15.110001 14.171619
15.650795 15.064346
16.451661 15.516118
16.7...

output:

417.780090341513

result:

ok found '417.7800903', expected '417.7800903', error '0.0000000'

Test #11:

score: 0
Accepted
time: 7ms
memory: 4264kb

input:

355
0.898520 0.132317
1.673138 0.997363
2.579144 1.000750
2.725149 1.089989
3.186200 1.347006
4.160982 2.336638
4.381893 3.282205
4.974331 3.376387
5.906150 3.588455
5.945502 4.454342
6.885385 4.626478
7.086844 4.838983
7.696701 5.451653
8.455143 5.635593
9.020368 5.796156
9.628724 6.016214
10.38331...

output:

654.398725108312

result:

ok found '654.3987251', expected '654.3987251', error '0.0000000'

Test #12:

score: 0
Accepted
time: 7ms
memory: 4344kb

input:

474
0.336050 0.700136
0.942726 1.619200
0.973510 2.168589
1.828522 2.427970
2.194275 3.313492
3.060666 4.012349
6.987523 8.944252
7.862245 9.378404
7.907362 12.303546
7.937320 12.736164
8.000283 13.427269
9.296230 18.611130
10.241402 19.336005
10.967422 19.343645
11.390036 20.009828
12.050751 20.823...

output:

844.284999245804

result:

ok found '844.2849992', expected '844.2849992', error '0.0000000'

Test #13:

score: 0
Accepted
time: 20ms
memory: 4332kb

input:

637
0.581818 0.380820
1.472864 0.432156
5.597870 6.252000
5.852848 6.787865
6.490892 6.991720
7.313168 7.482724
7.984231 7.779260
8.928339 7.789265
9.373078 8.287144
9.977861 8.715585
10.759909 9.200406
14.928051 14.368795
15.315810 15.271771
16.204773 15.373427
16.623238 15.664849
16.816516 16.6218...

output:

1216.761219704321

result:

ok found '1216.7612197', expected '1216.7612197', error '0.0000000'

Test #14:

score: 0
Accepted
time: 26ms
memory: 4252kb

input:

768
0.787902 0.396926
1.639123 1.051949
2.249225 1.952455
2.939336 2.269400
3.097246 2.605928
4.007878 3.090460
8.559656 5.137149
8.991805 5.225244
9.382946 5.886999
10.112782 6.755425
11.060352 7.355201
17.016206 10.025943
17.151609 10.962151
17.710678 11.658518
18.346906 12.522149
18.894902 13.501...

output:

1361.028899574542

result:

ok found '1361.0288996', expected '1361.0288996', error '0.0000000'

Test #15:

score: 0
Accepted
time: 30ms
memory: 4288kb

input:

859
5.225701 0.715370
5.677789 1.167429
5.967802 1.939990
5.997404 2.217704
6.600841 3.105107
6.880318 4.028506
7.739560 4.474905
8.303422 4.837790
8.735943 4.874449
8.814211 4.899976
9.283350 4.970867
9.873916 5.630578
10.017048 6.325429
10.196785 6.830584
10.392549 7.048678
10.893864 7.576400
11.0...

output:

1531.992517472620

result:

ok found '1531.9925175', expected '1531.9925175', error '0.0000000'

Test #16:

score: 0
Accepted
time: 35ms
memory: 4236kb

input:

867
0.035121 0.226069
0.167750 0.402102
0.681010 0.737773
1.453854 0.757372
1.812262 1.318469
2.112259 2.142797
2.130529 2.771977
2.587028 2.973341
7.036217 8.791798
7.650317 9.078014
8.428585 9.964787
8.597413 10.947425
8.650851 11.560847
8.743305 11.655952
9.204721 12.274110
9.233993 12.842222
9.3...

output:

1606.000475033144

result:

ok found '1606.0004750', expected '1606.0004750', error '0.0000000'

Test #17:

score: 0
Accepted
time: 33ms
memory: 4264kb

input:

879
0.314412 0.714527
0.867816 1.614100
1.456890 2.164042
2.166346 2.202811
6.851650 6.926119
7.337525 7.246755
7.635888 7.922303
8.272626 8.919706
8.733974 9.393703
9.615900 10.220938
10.109992 10.828200
10.902438 13.730242
11.348628 13.755023
12.255593 14.550624
15.252852 17.264662
15.455412 17.80...

output:

1648.435750117095

result:

ok found '1648.4357501', expected '1648.4357501', error '0.0000000'

Test #18:

score: 0
Accepted
time: 36ms
memory: 4324kb

input:

930
5.552506 2.177491
6.346565 3.078826
6.538814 3.215813
6.699836 3.598223
7.611589 3.851092
9.514428 6.289413
10.450077 7.008804
11.031837 7.020276
11.789820 7.092259
12.431858 8.044641
13.227881 8.289673
18.837722 13.331526
19.059026 14.125576
19.130549 14.194247
21.000426 17.733439
24.723623 23....

output:

1710.915657941826

result:

ok found '1710.9156579', expected '1710.9156579', error '0.0000000'

Test #19:

score: 0
Accepted
time: 38ms
memory: 4328kb

input:

892
0.827510 0.806765
1.050523 1.792928
1.868569 2.151983
1.965958 2.628842
2.369508 3.525255
2.636893 4.226109
3.217516 4.302298
3.246145 4.947053
3.628408 5.287972
4.451004 5.921280
4.728405 6.523436
5.245092 7.500100
5.979131 7.801388
6.146557 7.971759
6.985632 8.376414
7.494302 8.435857
7.919566...

output:

1652.111011705217

result:

ok found '1652.1110117', expected '1652.1110117', error '0.0000000'

Test #20:

score: 0
Accepted
time: 38ms
memory: 4256kb

input:

908
0.030931 0.714696
0.969056 0.783829
1.067604 0.851624
1.360877 1.577893
1.522654 1.584686
2.460712 1.706655
3.345580 2.384293
4.189521 2.709122
4.643588 3.276360
4.975268 3.558930
5.925376 3.823667
6.650388 3.991372
6.797897 4.156109
7.469445 4.688560
8.459404 4.984982
8.944370 5.023856
9.505585...

output:

1600.174012420831

result:

ok found '1600.1740124', expected '1600.1740124', error '0.0000000'

Test #21:

score: 0
Accepted
time: 36ms
memory: 4340kb

input:

913
3.266254 3.843936
4.004843 4.444039
4.324902 5.071691
8.420778 10.693918
8.943878 11.433393
9.107071 11.601072
10.039701 12.493401
10.290167 12.705980
11.022379 13.314759
11.768320 13.877547
12.066884 14.280865
12.523843 14.754650
12.677407 15.088401
12.994766 15.872152
13.370588 15.999932
13.95...

output:

1604.096575339401

result:

ok found '1604.0965753', expected '1604.0965753', error '0.0000000'

Test #22:

score: 0
Accepted
time: 38ms
memory: 4340kb

input:

922
0.019565 0.557995
0.075969 0.670366
4.537859 3.528593
5.370162 3.595681
5.503066 3.715154
5.526690 4.064795
5.763614 4.169008
6.481973 4.630387
7.111738 5.311894
7.405365 5.582057
8.271105 6.519414
9.004289 12.066926
9.428100 12.236266
10.281031 12.654266
10.469649 13.586800
11.322997 14.194498
...

output:

1583.943144678861

result:

ok found '1583.9431447', expected '1583.9431447', error '0.0000000'

Test #23:

score: 0
Accepted
time: 40ms
memory: 4324kb

input:

934
0.884270 0.149717
1.539799 0.698317
1.729711 1.127190
2.308326 1.178548
3.292672 1.694829
3.330271 2.464045
3.824140 3.119510
4.418809 3.587554
4.730924 4.305340
9.428477 7.658792
10.380325 8.474093
11.322849 9.361376
11.889628 9.966373
12.206870 10.609310
14.308053 13.864188
14.809249 13.916635...

output:

1688.956204628464

result:

ok found '1688.9562046', expected '1688.9562046', error '0.0000000'

Test #24:

score: 0
Accepted
time: 46ms
memory: 4260kb

input:

1000
0.961336 0.491460
1.651225 0.680713
2.327102 1.015668
2.592572 1.306494
3.455168 1.792800
3.471215 2.282722
3.529073 3.273872
4.069826 4.114567
4.616598 4.338919
4.940932 4.797458
5.704646 5.242569
6.338213 5.319637
6.986452 5.565660
7.931604 5.982119
8.747006 6.425918
9.568463 6.434943
9.60322...

output:

1782.541058356691

result:

ok found '1782.5410584', expected '1782.5410584', error '0.0000000'

Test #25:

score: 0
Accepted
time: 48ms
memory: 4328kb

input:

1000
0.855565 0.558584
4.611234 2.876625
5.214442 3.109442
5.889299 3.466168
6.390875 3.897954
7.079422 4.666450
11.262574 8.330252
11.532100 8.357679
12.309253 9.069734
12.692437 9.746308
13.445891 9.860003
13.505205 10.817262
13.759527 12.176588
13.814235 12.854345
14.005809 13.827446
14.086307 13...

output:

1889.301436344590

result:

ok found '1889.3014363', expected '1889.3014363', error '0.0000000'

Test #26:

score: 0
Accepted
time: 45ms
memory: 4200kb

input:

1000
0.884691 0.858065
1.796038 1.715983
2.283105 2.122190
2.417824 2.829541
6.395998 4.221731
7.053838 4.342162
7.875967 4.844847
8.144841 5.163648
9.078381 6.002118
9.337930 6.265439
10.064018 7.069143
10.684241 7.494127
11.453771 8.028080
11.735737 8.735653
16.793821 12.226616
16.832211 13.176341...

output:

1777.738827741561

result:

ok found '1777.7388277', expected '1777.7388277', error '0.0000000'

Test #27:

score: 0
Accepted
time: 42ms
memory: 4328kb

input:

1000
0.553645 0.737839
0.892345 1.214796
1.071757 1.318854
1.511528 2.216363
2.497889 2.644883
3.172381 3.202485
4.477868 5.483597
5.373205 6.345920
5.724722 6.549390
6.601601 6.951950
12.430718 10.909363
13.218873 11.360277
13.680609 12.347555
17.766986 15.156388
18.557273 15.868062
18.650111 16.74...

output:

1680.736193302480

result:

ok found '1680.7361933', expected '1680.7361933', error '0.0000000'

Test #28:

score: 0
Accepted
time: 46ms
memory: 4240kb

input:

1000
0.171678 0.286910
0.758013 1.107570
1.199299 1.321675
2.116410 1.534630
2.358257 2.404619
3.212135 2.688933
3.284423 3.662355
3.706035 3.812505
3.822695 4.539824
4.015809 5.404323
4.540777 6.266486
7.760307 7.123537
12.017082 11.230143
15.927340 16.105021
16.262605 16.262198
16.811031 16.613599...

output:

1858.058261276098

result:

ok found '1858.0582613', expected '1858.0582613', error '0.0000000'

Extra Test:

score: 0
Extra Test Passed