QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#361217#4573. Global Warmingmc020207#WA 309ms54444kbC++173.7kb2024-03-22 22:35:502024-03-22 22:35:51

Judging History

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

  • [2024-03-22 22:35:51]
  • 评测
  • 测评结果:WA
  • 用时:309ms
  • 内存:54444kb
  • [2024-03-22 22:35:50]
  • 提交

answer

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = (a); i <= (b);i++)
#define Rof(i, a, b) for(int i = (a); i >= (b);i--)
#define ll long long
#define lll __int128_t
#define db double
#define pii pair<int,int>
using namespace std;
template<class T1,class T2> void chkmin(T1 &x,T2 y){if(y<x)x=y;}
template<class T1,class T2> void chkmax(T1 &x,T2 y){if(y>x)x=y;}
const int N=100005;
db sqr(db x){return x*x;}
struct vec3{ll x,y,z;}p[N];
vec3 operator +(vec3 a,vec3 b){return {a.x+b.x,a.y+b.y,a.z+b.z};}
vec3 operator -(vec3 a,vec3 b){return {a.x-b.x,a.y-b.y,a.z-b.z};}
vec3 operator /(vec3 a,vec3 b){return {a.y*b.z-a.z*b.y,a.z*b.x-a.x*b.z,a.x*b.y-a.y*b.x};}
db abs(vec3 a){return sqrt((db)((lll)a.x*a.x+(lll)a.y*a.y+(lll)a.z*a.z));}
int bcj[N];
int ask(int x){return bcj[x]==x?x:bcj[x]=ask(bcj[x]);}
struct vec3db
{
    db x,y,z;
    db f(int t){return x*t*t+y*t+z;}
}pol[N];
vec3db operator +(vec3db a,vec3db b){return {a.x+b.x,a.y+b.y,a.z+b.z};}
vec3db operator -(vec3db a,vec3db b){return {a.x-b.x,a.y-b.y,a.z-b.z};}
int n,m,q,tofp[N];
map<pii,int> ma;
struct eve{int t,opt,x,y; vec3db p;}e[N*10];
db ans[N];
int lene;
void checkedge(int x,int y,int id)
{
    if(ma.count({x,y}))e[++lene]={(int)max(p[x].z,p[y].z)-1,2,ma[{x,y}],id,0,0,0};
    else ma[{x,y}]=ma[{y,x}]=id;
}
int main()
{
    scanf("%d",&n);
    For(i,1,n)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        p[i]={x,y,z};
    }
    scanf("%d",&m);
    For(i,1,m)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        tofp[x]=i; tofp[y]=i; tofp[z]=i;
        checkedge(x,y,i);
        checkedge(y,z,i);
        checkedge(z,x,i);
        db s=abs((p[x]-p[y])/(p[x]-p[z]))/2;
        int a[3]={p[x].z,p[y].z,p[z].z};
        sort(a,a+3);
        if(a[0]==a[2])e[++lene]={a[0],1,i,0,0,0,s};
        else if(a[0]==a[1])
        {
            s/=sqr(a[2]-a[0]);
            e[++lene]={a[2],1,i,0,s,-2*a[2]*s,sqr(a[2])*s};
            e[++lene]={a[0],1,i,0,-s,2*a[2]*s,(sqr(a[2]-a[0])-sqr(a[2]))*s};
        }
        else if(a[1]==a[2])
        {
            s/=sqr(a[2]-a[0]);
            e[++lene]={a[2],1,i,0,-s,2*a[0]*s,(sqr(a[2]-a[0])-sqr(a[0]))*s};
            e[++lene]={a[0],1,i,0,s,-2*a[0]*s,sqr(a[0])*s};
        }
        else
        {
            db s1=s/(a[2]-a[0])/(a[2]-a[1]);
            e[++lene]={a[2],1,i,0,s1,-2*a[2]*s1,sqr(a[2])*s1};
            e[++lene]={a[1],1,i,0,-s1,2*a[2]*s1,(sqr(a[2]-a[1])-sqr(a[2]))*s1};
            db s2=s/(a[2]-a[0])/(a[1]-a[0]);
            e[++lene]={a[1],1,i,0,-s2,2*a[0]*s2,(sqr(a[1]-a[0])-sqr(a[0]))*s2};
            e[++lene]={a[0],1,i,0,s2,-2*a[0]*s2,sqr(a[0])*s2};
        }
    }
    scanf("%d",&q);
    For(i,1,q)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        e[++lene]={x,0,y,i,0,0,0};
    }
    sort(e+1,e+lene+1,[](eve a,eve b){return a.t==b.t?a.opt>b.opt:a.t>b.t;});
    For(i,1,m)bcj[i]=i;
    For(i,1,lene)
    {
        // printf("%d %d %d %d %.2lf %.2lf %.2lf\n",e[i].t,e[i].opt,e[i].x,e[i].y,e[i].p.x,e[i].p.y,e[i].p.z);
        if(e[i].opt==2)
        {
            int x=ask(e[i].x),y=ask(e[i].y);
            if(x!=y)
            {
                bcj[y]=x;
                pol[x]=pol[x]+pol[y];
            }
        }
        else if(e[i].opt==1)
        {
            int x=ask(e[i].x);
            pol[x]=pol[x]+e[i].p;
        }
        else
        {
            int t=e[i].t,x=e[i].x,y=e[i].y;
            int xx=ask(tofp[x]);
            // printf("x=%d,xx=%d,%.2lf %.2lf %.2lf\n",x,xx,pol[xx].x,pol[xx].y,pol[xx].z);
            if(p[x].z<=t)ans[y]=-1;
            else ans[y]=pol[ask(tofp[x])].f(t);
        }
    }
    For(i,1,q)
        if(ans[i]<0)printf("-1\n");
        else printf("%.10lf\n",ans[i]);
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 10212kb

input:

5
0 0 0
2 0 0
2 2 0
0 2 0
1 1 4
4
1 2 5
2 3 5
3 4 5
4 1 5
7
0 1
0 5
1 5
2 5
3 5
4 5
5 5

output:

-1
16.4924225025
9.2769876576
4.1231056256
1.0307764064
-1
-1

result:

ok 7 numbers

Test #2:

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

input:

16
0 5 0
1 2 0
2 5 5
3 7 0
4 0 0
4 3 5
5 5 1
6 2 0
6 6 5
7 4 4
7 8 0
8 2 0
9 4 0
4 6 4
6 3 3
2 4 5
22
11 10 9
12 8 10
2 6 5
9 10 7
8 15 6
16 3 6
15 6 7
7 3 14
8 10 15
11 13 10
16 6 2
12 10 13
10 7 15
16 3 2
3 4 1
14 7 9
11 9 4
3 6 7
5 6 8
14 4 3
3 1 2
9 4 14
7
0 7
1 7
1 16
2 10
3 9
4 16
5 16

output:

120.4834053543
-1
93.9298952225
68.1819196635
40.9185614741
11.0674417909
-1

result:

ok 7 numbers

Test #3:

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

input:

9
0 0 0
0 1 0
0 2 0
1 0 0
1 1 10
1 2 0
2 0 0
2 1 0
2 2 0
8
4 8 5
5 9 8
8 4 7
1 2 5
2 6 3
9 6 5
6 2 5
1 5 4
5
9 5
0 5
3 5
3 5
2 5

output:

0.3427719812
34.2771981210
16.7958270793
16.7958270793
21.9374067974

result:

ok 5 numbers

Test #4:

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

input:

100
0 0 0
0 1 0
0 2 0
0 3 0
0 4 0
0 5 0
0 6 0
0 7 0
0 8 0
0 9 0
1 0 0
1 1 3
1 2 3
1 3 3
1 4 3
1 5 3
1 6 3
1 7 3
1 8 3
1 9 0
2 0 0
2 1 3
2 2 1
2 3 4
2 4 5
2 5 5
2 6 5
2 7 5
2 8 3
2 9 0
3 0 0
3 1 3
3 2 4
3 3 5
3 4 7
3 5 7
3 6 6
3 7 5
3 8 3
3 9 0
4 0 0
4 1 1
4 2 4
4 3 6
4 4 8
4 5 6
4 6 3
4 7 5
4 8 3
4 ...

output:

81.6704137546
183.3667939331
33.4906926470
183.3667939331
183.3667939331

result:

ok 5 numbers

Test #5:

score: -100
Wrong Answer
time: 309ms
memory: 54444kb

input:

49729
0 0 0
0 1234 0
0 2468 0
0 3702 0
0 4936 0
0 6170 0
0 7404 0
0 8638 0
0 9872 0
0 11106 0
0 12340 0
0 13574 0
0 14808 0
0 16042 0
0 17276 0
0 18510 0
0 19744 0
0 20978 0
0 22212 0
0 23446 0
0 24680 0
0 25914 0
0 27148 0
0 28382 0
0 29616 0
0 30850 0
0 32084 0
0 33318 0
0 34552 0
0 35786 0
0 3702...

output:

28336022114792.7539062500
-1
9067597268.2014770508
29490770935284.5585937500
21397921724095.1562500000
-1
414425634047.6392822266
-1
-1
-1
-1
-1
30771157933943.7226562500
-1
25468403653000.1953125000
-1
-1
16769145554604.0000000000
-1
-1
31149212820079.0390625000
31077512125207.3476562500
-1
6772280...

result:

wrong answer 2502nd numbers differ - expected: '2.2145359', found: '2.2145309', error = '0.0000022'