QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#787364#9808. Fragile PinballquailtyAC ✓2032ms4060kbC++233.6kb2024-11-27 11:19:502024-11-27 11:19:57

Judging History

This is the latest submission verdict.

  • [2024-11-27 11:19:57]
  • Judged
  • Verdict: AC
  • Time: 2032ms
  • Memory: 4060kb
  • [2024-11-27 11:19:50]
  • Submitted

answer

#pragma GCC optimize("Ofast","unroll-loops","fast-math")
#include <bits/stdc++.h>
using namespace std;
typedef double ld;
const ld eps=1e-8;
typedef pair<ld,ld> pnt;
#define x first
#define y second
#define fi first
#define se second
typedef vector<pnt> poly;
pnt operator - (pnt a,pnt b) {
    return pnt(a.x-b.x,a.y-b.y);
}
pnt operator + (pnt a,pnt b) {
    return pnt(a.x+b.x,a.y+b.y);
}
ld cross(pnt a,pnt b) {
    return a.x*b.y-a.y*b.x;
}
ld dot(pnt a,pnt b) {
    return a.x*b.x+a.y*b.y;
}
ld len2(pnt a) {
    return dot(a,a);
}
ld len(pnt a) {
    auto t=len2(a);
    if(t<0) t=0;
    return sqrt(t);
}
pnt rot(pnt a) {
    return pnt(-a.y,a.x);
}
pnt operator * (pnt a,ld k) {
    return pnt(a.x*k,a.y*k);
}
pnt operator / (pnt a,ld k) {
    return pnt(a.x/k,a.y/k);
}
pnt rf(pnt a,pnt b,pnt c) {
    ld co=cross(b-a,c-a);
    pnt t=rot(b-a);
    return c-t*co/len2(t)*2;
}
poly rf(poly a,int u) {
    pnt A(a[u]),B(a[(u+1)%a.size()]);
    for(auto&x:a) x=rf(A,B,x);
    return a;
}
int n;
pair<pnt,pnt> st,ed;
vector<pair<pnt,pnt>> ms;
pnt lineinter(pnt s1,pnt e1,pnt s2,pnt e2) {
    ld co=cross(e1-s1,e2-s2);
    if(abs(co)<eps) return pnt(1e9,1e9);
    auto p=cross(e1-s2,e2-s2);
    auto q=cross(e2-s2,s1-s2);
    return (s1*p+e1*q)/co;
}
bool onseg(pnt s,pnt e,pnt p) {
    return abs(cross(s-p,e-p))<eps&&dot(p-s,p-e)<eps;
}
int sgn(ld x) {
    if(x>eps) return 1;
    if(x<-eps) return -1;
    return 0;
}
bool seginter(pnt a,pnt b,pnt c,pnt d) {
    ld oa=cross(d-c,a-c),ob=cross(d-c,b-c);
    ld oc=cross(b-a,c-a),od=cross(b-a,d-a);
    if(sgn(oa)*sgn(ob)<0&&sgn(oc)*sgn(od)<0) return 1;
    if(onseg(c,d,a)||onseg(c,d,b)||onseg(a,b,c)||onseg(a,b,d)) return 1;
    return 0;
}
ld ans[1000];
void chk(int d) {
    vector<pnt> G;
    for(auto&x:ms) G.push_back(x.fi),G.push_back(x.se);
    G.push_back(st.fi); G.push_back(st.se);
    G.push_back(ed.fi); G.push_back(ed.se);
    vector<pair<pnt,pnt>> mss=ms;
    // for(auto &t:mss) {
    //     // extend everything by eps
    //     pnt&s=t.fi,&e=t.se;
    //     pnt v=e-s; v=v/(len(v))*eps;
    //     s=s-v; e=e+v;
    // }
    set<pair<pnt,pnt>> XX;
    for(int i=0;i<G.size();++i) {
        for(int j=i+1;j<G.size();++j) {
            pnt ss=G[i],ee=G[j];
            pnt SS=lineinter(st.fi,st.se,ss,ee);
            pnt EE=lineinter(ed.fi,ed.se,ss,ee);
            for(auto S:{SS,st.fi,st.se}) for(auto E:{EE,ed.fi,ed.se}) {
                if(len2(S-E)<ans[d]) continue;
                if(XX.count({S,E})) continue;
                XX.insert({S,E});
                if(!onseg(st.fi,st.se,S)) continue;
                if(!onseg(ed.fi,ed.se,E)) continue;
                // check if it crosses all segs
                bool ok=1;
                for(auto&x:mss) if(!seginter(S,E,x.fi,x.se)) {ok=0; break;}
                if(ok) {
                    ans[d]=max(ans[d],len2(S-E));
                }
            }
        }
    }
}
void dfs(poly a,int vis) {
    for(int i=0;i<n;++i) {
        ed={a[i],a[(i+1)%n]};
        chk(__builtin_popcount(vis));
    }
    for(int i=0;i<n;++i) if(!(vis&(1<<i))) {
        ms.push_back({a[i],a[(i+1)%n]});
        auto t=rf(a,i);
        dfs(t,vis|(1<<i));
        ms.pop_back();
    }
}
poly a;
int main() {
    cin>>n;
    for(int i=0;i<n;++i) {
        int x,y; cin>>x>>y;
        a.push_back(pnt(x,y));
    }
    for(int i=0;i<n;++i) {
        st={a[i],a[(i+1)%n]};
        dfs(a,0);
    }
    ld g=ans[0];
    for(int i=0;i<=n;++i) {
        g=max(g,ans[i]);
        printf("%.10Lf\n",sqrtl(g));
    }
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
4 0
0 3
0 -1

output:

5.0000000000
8.0000000000
8.8681850388
12.2100248109

result:

ok 4 numbers

Test #2:

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

input:

3
4 0
0 3
0 2

output:

5.0000000000
5.3665631460
6.1119191385
6.7822033044

result:

ok 4 numbers

Test #3:

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

input:

3
4 0
0 3
0 1

output:

5.0000000000
6.1846584384
7.1952235427
8.6534394993

result:

ok 4 numbers

Test #4:

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

input:

3
62 -12
-48 100
-45 -96

output:

196.0229578391
312.0417378328
326.2784777188
452.8071237291

result:

ok 4 numbers

Test #5:

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

input:

3
90 99
-76 -57
99 84

output:

227.7981562700
274.3523064578
306.8917794771
330.1051855464

result:

ok 4 numbers

Test #6:

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

input:

3
-67 22
-86 12
-81 -12

output:

36.7695526217
39.5639750057
50.9168559171
72.2775855175

result:

ok 4 numbers

Test #7:

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

input:

3
71 -48
-81 2
-83 -44

output:

160.0124995118
308.0567945676
308.0567945676
308.0567945676

result:

ok 4 numbers

Test #8:

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

input:

3
44 -44
-31 -77
8 -98

output:

81.9390017025
115.7926682998
125.6060440299
167.9364934970

result:

ok 4 numbers

Test #9:

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

input:

3
40 91
-42 90
-5 -99

output:

195.2562418977
378.8742667920
378.8742667920
378.8742667920

result:

ok 4 numbers

Test #10:

score: 0
Accepted
time: 11ms
memory: 3972kb

input:

4
-10 -97
13 -98
90 50
42 97

output:

200.8482013860
269.6873414653
382.1660680405
476.5992628304
476.5992628304

result:

ok 5 numbers

Test #11:

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

input:

4
39 89
-72 -94
87 -58
90 36

output:

214.0327077808
413.7441466099
413.7441466099
502.9657182485
595.0182126549

result:

ok 5 numbers

Test #12:

score: 0
Accepted
time: 5ms
memory: 3824kb

input:

4
-6 -90
33 -75
4 97
-36 -69

output:

187.2671887972
269.5494443974
309.2080577955
364.7016580716
395.3782875544

result:

ok 5 numbers

Test #13:

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

input:

4
44 81
27 81
60 -57
83 3

output:

141.8908030846
187.1227149599
251.4766895481
274.1276568435
286.3195174057

result:

ok 5 numbers

Test #14:

score: 0
Accepted
time: 5ms
memory: 4024kb

input:

4
96 -13
99 1
-67 -36
67 -37

output:

170.0735135169
183.0854262490
223.2121035172
277.3791841974
306.1503972704

result:

ok 5 numbers

Test #15:

score: 0
Accepted
time: 6ms
memory: 3952kb

input:

4
-18 -98
80 -59
73 68
-78 -62

output:

199.2510978640
378.3258788244
378.3258788244
512.6175438119
557.3874576159

result:

ok 5 numbers

Test #16:

score: 0
Accepted
time: 118ms
memory: 3780kb

input:

5
-90 41
-93 27
94 79
83 91
-44 94

output:

194.0953373989
206.3555244544
256.7313020009
337.3469034623
377.9291604083
396.6629386606

result:

ok 6 numbers

Test #17:

score: 0
Accepted
time: 67ms
memory: 3836kb

input:

5
78 -95
96 29
-95 34
-76 -82
64 -95

output:

215.8008341040
379.4743518267
555.0747894795
584.0075273162
640.7094383943
693.1724916029

result:

ok 6 numbers

Test #18:

score: 0
Accepted
time: 56ms
memory: 3892kb

input:

5
45 -26
38 62
-31 57
-40 -43
-13 -91

output:

161.2761606686
297.8277729918
329.1035322799
455.4198197859
496.8587774603
600.6721130631

result:

ok 6 numbers

Test #19:

score: 0
Accepted
time: 60ms
memory: 3916kb

input:

5
-28 78
-63 63
-85 30
-7 -80
61 -77

output:

187.0187156410
342.3719736956
437.2830840034
525.9782779688
704.0644536416
704.0644536416

result:

ok 6 numbers

Test #20:

score: 0
Accepted
time: 143ms
memory: 3840kb

input:

5
-20 91
-21 90
4 -99
18 -92
41 57

output:

191.5097908724
232.3855250971
282.2360792992
389.3067011893
404.0751959464
477.0512357975

result:

ok 6 numbers

Test #21:

score: 0
Accepted
time: 62ms
memory: 3912kb

input:

5
40 -91
65 75
-50 -86
-48 -87
27 -96

output:

197.8534811420
296.4229333520
328.6536876671
385.6300362565
404.1760170445
404.1760170445

result:

ok 6 numbers

Test #22:

score: 0
Accepted
time: 699ms
memory: 3880kb

input:

6
86 57
51 69
2 -52
18 -100
89 -84
87 33

output:

172.1917535772
341.1351351351
400.6660747466
501.2681880748
565.6089851553
622.6908443617
665.7005715733

result:

ok 7 numbers

Test #23:

score: 0
Accepted
time: 636ms
memory: 3876kb

input:

6
99 49
88 89
55 54
23 -38
18 -72
84 -63

output:

175.5591068558
264.0790240027
313.6562336529
390.4545922587
470.7520123025
521.8309234009
550.7688272207

result:

ok 7 numbers

Test #24:

score: 0
Accepted
time: 692ms
memory: 3792kb

input:

6
53 36
-5 100
-56 98
-79 14
-84 -24
73 -27

output:

179.6273921205
314.8627860318
385.3436584536
493.1936304148
606.1814738093
673.3088187665
673.3088187665

result:

ok 7 numbers

Test #25:

score: 0
Accepted
time: 596ms
memory: 3972kb

input:

6
76 84
32 100
77 -80
91 -17
95 37
86 79

output:

185.5397531528
211.9073279451
264.7167552270
315.0624009010
324.8746052997
356.5263273519
356.5263273519

result:

ok 7 numbers

Test #26:

score: 0
Accepted
time: 1059ms
memory: 4056kb

input:

6
-35 12
-31 -22
-6 -81
96 -21
69 64
-29 65

output:

163.2482771731
291.5154358680
399.0101636438
496.2062910290
585.3237907385
681.2158835719
681.2158835719

result:

ok 7 numbers

Test #27:

score: 0
Accepted
time: 872ms
memory: 3988kb

input:

6
89 -75
97 1
8 95
-21 87
-23 -98
75 -87

output:

198.7259419402
382.9027214185
570.2673088223
699.3441453732
793.0270423195
950.4011888463
950.4011888463

result:

ok 7 numbers

Test #28:

score: 0
Accepted
time: 612ms
memory: 3852kb

input:

6
-69 88
-100 50
-100 -50
28 -25
70 26
65 90

output:

216.3908500838
349.4249571953
517.3648455359
604.9506993995
740.9268057663
867.5737615347
994.1760637116

result:

ok 7 numbers

Test #29:

score: 0
Accepted
time: 910ms
memory: 3904kb

input:

6
55 99
-32 6
-38 -60
89 -99
97 -98
81 73

output:

201.4274062783
379.4814155239
457.6725763898
590.7260778701
652.1915273794
771.7408992905
888.9512915726

result:

ok 7 numbers

Test #30:

score: 0
Accepted
time: 649ms
memory: 3852kb

input:

6
-64 25
-59 -69
23 -94
73 -88
98 20
92 89

output:

218.5520532962
371.4968243683
490.9959161077
639.6830728925
746.6559332906
869.8425549059
875.9512962851

result:

ok 7 numbers

Test #31:

score: 0
Accepted
time: 799ms
memory: 4056kb

input:

6
-62 -66
78 -48
99 89
73 94
-91 73
-89 -60

output:

239.8853893008
382.6215847482
560.8304105359
628.0561803055
749.5710496161
842.6483309958
933.0843337615

result:

ok 7 numbers

Test #32:

score: 0
Accepted
time: 591ms
memory: 4052kb

input:

6
91 49
68 88
-51 98
-95 35
-21 -72
92 -31

output:

198.3053201505
382.2029154598
500.5390662604
668.3903338665
835.2779703413
965.7870163759
1130.0060603206

result:

ok 7 numbers

Test #33:

score: 0
Accepted
time: 948ms
memory: 4000kb

input:

6
-49 -75
88 10
76 64
-97 46
-75 -62
-72 -67

output:

197.6486782147
371.8982185739
549.6917004399
696.6829667177
739.7642481293
784.4030441331
784.4030441331

result:

ok 7 numbers

Test #34:

score: 0
Accepted
time: 651ms
memory: 3856kb

input:

6
-100 90
-25 -88
85 -85
97 31
83 99
22 100

output:

254.6566315649
407.4606944530
579.3146427096
748.4509780585
833.0001737735
949.7470747562
1042.0294169897

result:

ok 7 numbers

Test #35:

score: 0
Accepted
time: 669ms
memory: 3788kb

input:

6
-61 98
-93 70
-98 34
-74 -94
94 -87
95 36

output:

244.1679749681
482.5898054808
586.6287200306
765.0810705511
925.8004481681
1083.6630619894
1146.0635064754

result:

ok 7 numbers

Test #36:

score: 0
Accepted
time: 1432ms
memory: 3900kb

input:

6
-86 -4
-39 -8
-6 -9
39 -6
25 8
-64 7

output:

125.0159989761
127.4278079971
142.2034926754
158.0354903888
158.0354903888
158.1714016049
168.5846623761

result:

ok 7 numbers

Test #37:

score: 0
Accepted
time: 99ms
memory: 3840kb

input:

5
69 -12
69 13
-24 17
-93 -2
-55 -14

output:

162.6929623555
324.0000000000
324.0000000000
329.0388656505
329.0388656505
331.9991891963

result:

ok 6 numbers

Test #38:

score: 0
Accepted
time: 55ms
memory: 3772kb

input:

5
26 46
-20 38
-23 22
-16 -75
24 -30

output:

128.0820049812
203.8214521471
251.1338131771
288.8230875765
341.5631917109
389.0906717525

result:

ok 6 numbers

Test #39:

score: 0
Accepted
time: 836ms
memory: 3856kb

input:

6
-58 -21
-46 -25
7 -25
45 -21
47 25
-82 17

output:

132.5631924782
257.0614932672
282.8153291618
340.9241087112
415.7344670877
415.7344670877
415.7344670877

result:

ok 7 numbers

Test #40:

score: 0
Accepted
time: 752ms
memory: 3868kb

input:

6
19 -61
36 -24
17 76
0 93
-31 52
-3 -93

output:

186.0241919751
203.1955613265
354.1959073806
369.5554858069
396.6353036668
500.3491356823
500.3491356823

result:

ok 7 numbers

Test #41:

score: 0
Accepted
time: 670ms
memory: 3852kb

input:

6
33 -70
44 32
-31 68
-35 25
-31 -50
8 -63

output:

152.1183749585
228.8549759127
330.2823466410
431.9255969480
439.7417145779
527.3331384235
546.3414218192

result:

ok 7 numbers

Test #42:

score: 0
Accepted
time: 643ms
memory: 4040kb

input:

6
10 94
-35 45
-23 -79
31 -51
37 -40
36 20

output:

176.1192777637
244.0822641601
326.0653631380
427.7768253798
478.0480555323
550.2325772129
559.5812477289

result:

ok 7 numbers

Test #43:

score: 0
Accepted
time: 713ms
memory: 3892kb

input:

6
63 -31
42 46
-79 -26
-67 -31
-10 -52
8 -52

output:

142.0880009009
271.3617511736
284.2910861706
342.0566184464
427.9420882192
428.7399182648
428.7399182648

result:

ok 7 numbers

Test #44:

score: 0
Accepted
time: 656ms
memory: 3924kb

input:

6
4 58
-5 -64
88 -16
93 1
67 41
16 59

output:

127.3145710435
245.9540670063
306.9154305428
382.5950578644
469.2786412084
473.9269914441
473.9269914441

result:

ok 7 numbers

Test #45:

score: 0
Accepted
time: 1550ms
memory: 3900kb

input:

6
-30 -90
7 -96
47 -35
56 -12
43 68
33 80

output:

181.2980970667
355.7848284119
357.5712413962
373.8688157580
502.9721507643
502.9721507643
502.9721507643

result:

ok 7 numbers

Test #46:

score: 0
Accepted
time: 576ms
memory: 3928kb

input:

6
-34 72
-47 -49
-43 -51
23 -73
95 -13
44 69

output:

155.8011553231
295.7651926450
422.4250524804
529.5290106190
660.5282383944
761.6865723001
886.2322390937

result:

ok 7 numbers

Test #47:

score: 0
Accepted
time: 657ms
memory: 3848kb

input:

6
87 16
60 72
-64 -64
-3 -99
30 -94
48 -82

output:

184.0434731252
359.3457864759
406.6975111068
521.1155610335
629.6836165983
629.6836165983
629.6836165983

result:

ok 7 numbers

Test #48:

score: 0
Accepted
time: 739ms
memory: 3896kb

input:

6
82 10
30 91
-49 73
-41 -85
57 -77
80 -22

output:

189.7814532561
339.8634311984
507.0046977264
598.8042191184
691.7927482513
736.1351625104
745.7922736150

result:

ok 7 numbers

Test #49:

score: 0
Accepted
time: 731ms
memory: 3852kb

input:

6
10 -88
92 -12
94 -3
70 69
-94 -20
-22 -87

output:

188.7670522099
367.4566641116
489.9118296669
545.4472184477
667.4905804594
669.7245211873
679.2426782893

result:

ok 7 numbers

Test #50:

score: 0
Accepted
time: 1257ms
memory: 3900kb

input:

6
-5 82
-9 14
3 -92
6 -73
9 5
-1 98

output:

190.0421005988
190.6261913473
191.0936437603
191.0936437603
191.0936437603
191.0936437603
191.0936437603

result:

ok 7 numbers

Test #51:

score: 0
Accepted
time: 2032ms
memory: 3928kb

input:

6
3 98
-19 16
-2 -99
7 -92
19 21
14 68

output:

197.0634415613
200.8970927829
214.5502603578
235.2047330133
235.2047330133
251.7558323688
251.7558323688

result:

ok 7 numbers

Test #52:

score: 0
Accepted
time: 1513ms
memory: 3852kb

input:

6
17 80
11 92
-22 66
-23 -63
-5 -98
27 41

output:

190.6724940834
214.5433156758
292.3339490743
355.3784638136
379.5495129974
405.5014375019
405.5014375019

result:

ok 7 numbers

Test #53:

score: 0
Accepted
time: 682ms
memory: 3996kb

input:

6
28 25
-6 97
-29 14
-29 -14
3 -99
29 16

output:

196.2065238467
206.1084843403
215.8658112866
264.4386719351
318.8524286925
379.0442357681
420.5799350628

result:

ok 7 numbers

Test #54:

score: 0
Accepted
time: 952ms
memory: 3936kb

input:

6
4 99
-26 75
-15 -92
31 -60
31 61
12 95

output:

191.9426997830
241.1747357000
385.7637204163
417.3231872958
481.0229511896
551.6858809151
551.6858809151

result:

ok 7 numbers

Test #55:

score: 0
Accepted
time: 767ms
memory: 3900kb

input:

6
-11 -97
47 -28
39 60
-49 11
-49 -16
-19 -91

output:

164.7695360193
223.8187759767
314.9770081846
425.3515251681
459.1865506611
555.2890444114
555.2890444114

result:

ok 7 numbers

Test #56:

score: 0
Accepted
time: 820ms
memory: 4060kb

input:

6
18 93
-6 99
-14 -95
-5 -99
33 -74
49 0

output:

198.0025252364
285.1553507913
416.6616833042
490.4733473722
615.6567898736
653.3447246944
653.3447246944

result:

ok 7 numbers

Test #57:

score: 0
Accepted
time: 829ms
memory: 3788kb

input:

6
-24 58
-52 51
-79 -36
-53 -50
91 -24
96 -16

output:

176.1391495381
322.4164792890
409.0036321335
517.4857215429
626.3010407538
651.4205697517
697.6458654640

result:

ok 7 numbers

Test #58:

score: 0
Accepted
time: 622ms
memory: 3888kb

input:

6
11 69
-25 67
-91 -28
-4 -69
99 6
59 56

output:

193.0181338631
318.0072067253
446.7872168306
583.4370257009
669.4503593284
787.3212187204
801.9550992653

result:

ok 7 numbers

Test #59:

score: 0
Accepted
time: 641ms
memory: 3776kb

input:

6
-52 59
-62 54
-99 6
-91 -28
-18 -68
68 50

output:

177.1016657177
335.0530538390
390.1474030673
483.1226649486
629.1014815931
651.3402877501
651.3402877501

result:

ok 7 numbers

Test #60:

score: 0
Accepted
time: 636ms
memory: 3836kb

input:

6
8 -79
72 -55
94 -27
-55 66
-77 -50
-44 -71

output:

175.6416807025
349.2376736284
388.5445221752
504.0407044306
661.8618230343
661.8618230343
661.8618230343

result:

ok 7 numbers

Test #61:

score: 0
Accepted
time: 765ms
memory: 3932kb

input:

6
-14 98
-38 -90
-36 -91
-33 -92
89 -5
73 57

output:

190.9476368013
371.8851208100
546.2717267392
726.7733108966
726.7733108966
810.8102567789
821.8376963131

result:

ok 7 numbers

Test #62:

score: 0
Accepted
time: 741ms
memory: 3844kb

input:

6
-85 32
-75 -54
22 -96
47 -85
87 -22
89 -5

output:

180.2775637732
348.2980872051
513.8663511803
525.7346509379
698.9816543755
698.9816543755
698.9816543755

result:

ok 7 numbers

Test #63:

score: 0
Accepted
time: 616ms
memory: 3972kb

input:

6
94 -32
99 7
63 77
-94 33
-46 -88
68 -72

output:

198.9195817410
388.1133031646
531.4245989324
694.4195047124
777.1045293609
902.6499750605
953.1357593573

result:

ok 7 numbers

Extra Test:

score: 0
Extra Test Passed