QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#361217 | #4573. Global Warming | mc020207# | WA | 309ms | 54444kb | C++17 | 3.7kb | 2024-03-22 22:35:50 | 2024-03-22 22:35:51 |
Judging History
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'