QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#787364 | #9808. Fragile Pinball | quailty | AC ✓ | 2032ms | 4060kb | C++23 | 3.6kb | 2024-11-27 11:19:50 | 2024-11-27 11:19:57 |
Judging History
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