QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#400998 | #985. Attractions On Plane | grass8cow | WA | 8ms | 33804kb | C++17 | 2.3kb | 2024-04-27 20:41:22 | 2024-04-27 20:41:22 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,X;
#define pb push_back
vector<int>g[1001000];
int Z[200100];
int xp[1001000];
int m,t;
struct no{ll x,y;int z;}a[401000],b[401000];
no operator - (const no &a,const no &b){return (no){a.x-b.x,a.y-b.y,a.z-b.z};}
__int128 cro(no a,no b){return (__int128)a.x*b.y-(__int128)b.x*a.y;}
#define mp make_pair
#define F first
#define S second
#define db double
db ans[201000];
const db eps=1e-9;
int main(){
scanf("%d%d",&n,&X);
for(int i=1,l,y,r,h;i<=n;i++){
scanf("%d%d%d%d",&l,&y,&r,&h);r+=l;
Z[i]=y;ll y_=1ll*y*y+1ll*l*l;
a[++m]=(no){2*l,y_,i};
if(l==r)continue;
y_=1ll*y*y+1ll*r*r;
a[++m]=(no){2*r,y_,i};
//(x-l)^2+y^2
int L=max(0,l),R=min(X,r);
if(l<r)g[l].pb(i),g[r].pb(-i);
}
sort(a+1,a+m+1,[&](no a,no b){if(a.x!=b.x)return a.x<b.x;if(a.y<b.y)return a.y<b.y;return a.z<b.z;});
for(int i=1;i<=m;i++){
if(i>1&&a[i].x==a[i-1].x)continue;
while(t>1&&cro(b[t]-b[t-1],a[i]-b[t-1])<=0)t--;
b[++t]=a[i];
}
vector<pair<db,pair<int,int> > >jd;
int w=1;
while(w<t&&b[w].y>b[w+1].y)w++;
jd.pb(mp(0,mp(w,0)));
for(int i=w;i<t;i++)
jd.pb(mp(1.0*(b[i+1].y-b[i].y)/(b[i+1].x-b[i].x),mp(i+1,0)));
set<pair<int,int> >s;
for(int i=0;i<X;i++){
for(int o:g[i])if(o>0)s.insert(make_pair(Z[o],o));
else s.erase(make_pair(Z[-o],-o));
if(!s.empty())xp[i]=(*s.begin()).second;
if(i==0||xp[i]!=xp[i-1])jd.pb(mp(i,mp(xp[i],1)));
}
jd.pb(mp(X,mp(0,2)));
sort(jd.begin(),jd.end());
int v1=0,v2=0;int sz=jd.size();
for(int i=0;i<sz;i++){
auto it=jd[i];
if(it.S.S==2)break;
auto it2=jd[i+1];
if(it.S.S==0)v1=it.S.F;else v2=it.S.F;
if(!v1)continue;
db L=it.F,R=it2.F;
if(!v2)ans[b[v1].z]+=R-L;
else{
db p=-b[v1].x,q=b[v1].y-1ll*Z[v2]*Z[v2];
//x^2+px+q<0
db dt=p*p-q*4;
if(dt<eps)ans[v2]+=R-L;
else{
dt=sqrt(dt);
db kl=max(L,(-p-dt)/2),kr=min(R,(-p+dt)/2),lt=max(0.0,kr-kl);
ans[b[v1].z]+=lt,ans[v2]+=R-L-lt;
}
}
}
for(int i=1;i<=n;i++)printf("%.9lf\n",ans[i]/X*100);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 33536kb
input:
2 10 1 2 5 1 2 1 1 5
output:
52.679491924 47.320508076
result:
ok 2 numbers
Test #2:
score: 0
Accepted
time: 8ms
memory: 33432kb
input:
4 7 1 3 0 0 3 4 0 0 5 5 0 0 3 4 0 0
output:
53.571428571 35.714285714 10.714285714 0.000000000
result:
ok 4 numbers
Test #3:
score: 0
Accepted
time: 4ms
memory: 33804kb
input:
4 7 1 3 0 0 3 4 0 0 5 5 0 0 3 4 0 0
output:
53.571428571 35.714285714 10.714285714 0.000000000
result:
ok 4 numbers
Test #4:
score: 0
Accepted
time: 3ms
memory: 32948kb
input:
2 10 1 2 5 1 2 1 1 5
output:
52.679491924 47.320508076
result:
ok 2 numbers
Test #5:
score: 0
Accepted
time: 4ms
memory: 32452kb
input:
4 7 1 3 0 0 3 4 0 0 5 5 0 0 3 4 0 0
output:
53.571428571 35.714285714 10.714285714 0.000000000
result:
ok 4 numbers
Test #6:
score: 0
Accepted
time: 8ms
memory: 32592kb
input:
1 526993 64 7 0 0
output:
100.000000000
result:
ok found '100.0000000', expected '100.0000000', error '0.0000000'
Test #7:
score: 0
Accepted
time: 3ms
memory: 33540kb
input:
2 306235 19 8 0 0 21 6 0 0
output:
0.004245106 99.995754894
result:
ok 2 numbers
Test #8:
score: 0
Accepted
time: 5ms
memory: 33596kb
input:
3 795677 34 3 0 0 56 5 0 0 48 7 0 0
output:
0.005332386 99.993653203 0.001014410
result:
ok 3 numbers
Test #9:
score: 0
Accepted
time: 0ms
memory: 32732kb
input:
495 368130 723082 376716 0 0 723082 376716 0 0 723082 376716 0 0 723082 376716 0 0 723082 376716 0 0 723082 376716 0 0 723082 376716 0 0 723082 376716 0 0 723082 376716 0 0 723082 376716 0 0 723082 376716 0 0 723082 376716 0 0 723082 376716 0 0 723082 376716 0 0 723082 376716 0 0 723082 376716 0 0 7...
output:
100.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.00000000...
result:
ok 495 numbers
Test #10:
score: 0
Accepted
time: 4ms
memory: 32212kb
input:
493 261998 815225 6 0 0 806366 7 0 0 103518 4 0 0 229937 5 0 0 530734 7 0 0 127508 8 0 0 128550 6 0 0 614581 8 0 0 334911 8 0 0 258776 3 0 0 256449 5 0 0 702679 3 0 0 650973 9 0 0 309392 10 0 0 414347 6 0 0 867328 5 0 0 29525 5 0 0 912594 5 0 0 221324 7 0 0 907323 3 0 0 645853 8 0 0 482215 2 0 0 652...
output:
0.000000000 0.000000000 1.102300117 0.796382067 0.000000000 0.420799611 0.344091724 0.000000000 0.000000000 0.539136188 0.191448962 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.168908383 0.000000000 0.442178665 0.000000000 0.000000000 0.000000000 0.000000000 0.532803942 0.277126075 ...
result:
ok 493 numbers
Test #11:
score: 0
Accepted
time: 7ms
memory: 33588kb
input:
498 740195 539527 8 0 0 565139 7 0 0 138287 4 0 0 872252 2 0 0 416589 5 0 0 740672 5 0 0 774707 3 0 0 54007 5 0 0 621977 6 0 0 961953 7 0 0 48454 3 0 0 348868 2 0 0 703397 5 0 0 294082 9 0 0 928003 5 0 0 226018 10 0 0 794174 2 0 0 693633 5 0 0 796829 3 0 0 754094 1 0 0 116953 10 0 0 541832 10 0 0 72...
output:
0.426509629 0.069992639 0.094182581 0.000000000 0.218661293 0.676916163 0.000000000 0.164146267 0.584237768 0.000000000 0.258789899 0.215157864 0.167045749 0.183319459 0.000000000 0.127664572 0.000000000 0.221903359 0.000000000 0.000000000 0.101619431 0.262561304 0.250812740 0.117199120 0.176108007 ...
result:
ok 498 numbers
Test #12:
score: 0
Accepted
time: 4ms
memory: 33732kb
input:
494 839352 564592 4 0 0 161754 2 0 0 55284 10 0 0 338248 1 0 0 643821 3 0 0 928087 6 0 0 369743 10 0 0 303193 6 0 0 983594 7 0 0 623627 7 0 0 728262 6 0 0 691871 3 0 0 774980 1 0 0 373696 10 0 0 582836 1 0 0 26658 2 0 0 451863 9 0 0 804980 4 0 0 656996 5 0 0 899465 4 0 0 514790 7 0 0 527354 1 0 0 52...
output:
0.190150385 0.902065777 0.597363914 0.190982089 0.432477015 0.000000000 0.434856695 0.265138139 0.000000000 0.124297625 0.314646133 0.110986782 0.397096481 0.389342111 0.057071213 0.194064247 0.219869630 0.616249537 0.214094905 0.000000000 0.177159719 0.096445905 0.070770630 0.106861232 0.016989858 ...
result:
ok 494 numbers
Test #13:
score: 0
Accepted
time: 3ms
memory: 32648kb
input:
498 496147 152118 592509 0 0 993525 4837 0 0 785975 139262 0 0 899162 700698 0 0 171554 914518 0 0 929801 776817 0 0 214570 546465 0 0 55190 857202 0 0 947539 994980 0 0 721719 395723 0 0 93450 26935 0 0 99283 123727 0 0 479353 554490 0 0 628771 631484 0 0 21225 550099 0 0 141191 667118 0 0 305921 4...
output:
0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 9.795153103 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 ...
result:
ok 498 numbers
Test #14:
score: -100
Wrong Answer
time: 3ms
memory: 32980kb
input:
496 9632 100 6 0 0 67 10 0 0 40 6 0 0 30 5 0 0 52 2 0 0 14 5 0 0 47 3 0 0 91 8 0 0 59 10 0 0 75 6 0 0 52 2 0 0 34 2 0 0 84 5 0 0 63 1 0 0 9 6 0 0 33 4 0 0 63 6 0 0 92 5 0 0 31 4 0 0 29 9 0 0 29 10 0 0 83 5 0 0 6 9 0 0 53 2 0 0 32 3 0 0 42 1 0 0 100 2 0 0 57 8 0 0 82 8 0 0 73 10 0 0 63 5 0 0 100 2 0 ...
output:
0.000000000 0.000000000 0.000000000 0.000000000 0.010382060 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.007786545 0.000000000 0.039451827 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.000000000 0.015573090 0.000000000 ...
result:
wrong answer 5th numbers differ - expected: '0.0000000', found: '0.0103821', error = '0.0103821'