QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#400998#985. Attractions On Planegrass8cowWA 8ms33804kbC++172.3kb2024-04-27 20:41:222024-04-27 20:41:22

Judging History

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

  • [2024-04-27 20:41:22]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:33804kb
  • [2024-04-27 20:41:22]
  • 提交

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;
}

詳細信息

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'