QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#22013 | #2839. 3D Geometry | zmwang | AC ✓ | 134ms | 3776kb | C++20 | 5.9kb | 2022-03-08 21:38:44 | 2022-04-30 00:41:01 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<string>
#include<sstream>
#include<cctype>
#include<cmath>
#include<iomanip>
#include<map>
#include<stack>
#include<set>
#include<functional>
#define in(x) x=read()
#define qr read()
#define int ll
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
namespace fastIO
{
#define BUF_SIZE 100000
bool IOerror=0;
inline char nc()
{
static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
if (p1==pend){
p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin);
if (pend==p1){IOerror=1;return -1;}
}
return *p1++;
}
inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
inline ll read()
{
bool sign=0; char ch=nc();ll x=0;
for (;blank(ch);ch=nc());
if (IOerror)return 0;
if (ch=='-')sign=1,ch=nc();
for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
if (sign)x=-x;
return x;
}
#undef BUF_SIZE
};
using namespace fastIO;
#define x1 x[1]
#define x2 x[2]
#define x3 x[3]
#define x4 x[4]
#define y1 y[1]
#define y2 y[2]
#define y3 y[3]
#define y4 y[4]
#define z1 z[1]
#define z2 z[2]
#define z3 z[3]
#define z4 z[4]
int x[5],y[5],z[5];
struct node
{
double a,b,c,p;
int f;
}t[10];
bool cmp(const node& a,const node& b){return a.p<b.p;}
double calc(double a,double b,double c,double x)
{
return a*x*x*x+b*x*x+c*x;
}
signed main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
while(scanf("%lld%lld%lld",&x[1],&y[1],&z[1])!=EOF)
{
// scanf("%lld%lld",&y[1],&z[1]);
// y[1]=qr,z[1]=qr;
for(int i=2;i<=4;i++)
scanf("%lld%lld%lld",&x[i],&y[i],&z[i]);//in(x[i]),in(y[i]),in(z[i]);
// cout<<x1<<' '<<x2<<' '<<x3<<",,,,"<<x4<<'\n';
if(x1>x2)x1*=-1,x2*=-1,x3*=-1,x4*=-1;
if(y1>y2)y1*=-1,y2*=-1,y3*=-1,y4*=-1;
if(z1<z2)z1*=-1,z2*=-1,z3*=-1,z4*=-1;
if(x3>x4)swap(x3,x4);
if(y3>y4)swap(y3,y4);
if(z3>z4)swap(z3,z4);
if(x1>=x4||y1>=y4)
{
puts("0");
continue;
}
int nx=x4-x3,ny=y4-y3;
int num=0;
int lx=x4-x1,ly=y4-y1,dx=x3-x1,dy=y3-y1;
double kx=1.0*(x2-x1)/(z1-z2),ky=1.0*(y2-y1)/(z1-z2);
// cout<<x1<<' '<<x2<<' '<<x3<<",,,,"<<x4<<'\n';
// cout<<y1<<' '<<y2<<' '<<y3<<",,,,"<<y4<<'\n';
// cout<<kx<<",,,,,,,,"<<ky<<'\n';
int ff=0;
if(x1>=x3)
{
if(y1>=y3)
{
double t1=1.0*(x4-x1)/(x2-x1)*(z1-z2)+z2;
double t2=1.0*(y4-y1)/(y2-y1)*(z1-z2)+z2;
double t3=1.0*(y4-y1)/(y2-y1)*(z1-z2)+1.0*(x4-x1)/(x2-x1)*(z1-z2)+z2;
double p=kx*ky/2;
t[1].a=p,t[1].b=t[1].c=0,t[1].p=z2;
if(t1<=t2)
{
t[2].a=0,t[2].b=ky*lx,t[2].c=-ky*lx*lx/kx/2,t[2].p=t1;
t[3].a=-kx*ky/2,t[3].b=(kx*(ly+ky/kx*lx)+ky*(lx+kx/ky*ly))/2,t[3].c=lx*ly-(ly+ky/kx*lx)*(lx+kx/ky*ly)/2,t[3].p=t2;
}
else
{
t[2].a=0,t[2].b=kx*ly,t[2].c=-kx*ly*ly/ky/2,t[2].p=t2;
t[3].a=-kx*ky/2,t[3].b=(kx*(ly+ky/kx*lx)+ky*(lx+kx/ky*ly))/2,t[3].c=lx*ly-(ly+ky/kx*lx)*(lx+kx/ky*ly)/2,t[3].p=t1;
}
t[4].a=t[4].b=0,t[4].c=lx*ly,t[4].p=t3;
t[1].f=t[2].f=t[3].f=t[4].f=1;
}
else
{
double t1=dy/ky+z2;
double t3=ly/ky+z2;
double t2=lx/kx+dy/ky+z2;
double t4=lx/kx+ly/ky+z2;
t[1].a=kx*ky/2,t[1].b=-dy*kx,t[1].c=kx*dy*dy/ky/2,t[1].p=t1;
if(t3<=t2)
{
t[2].a=0,t[2].b=kx*ny,t[2].c=-(kx*ny*(ly+dy))/(2*ky),t[2].p=t3;
t[3].p=t2;
}
else
{
t[2].a=0,t[2].b=ky*lx,t[2].c=-lx*lx*ky/kx/2-dy*lx,t[2].p=t2;
t[3].p=t3;
}
t[3].a=-kx*ky/2,t[3].b=kx*ly+ky*lx,t[3].c=ny*lx-(ly+ky/kx*lx)*(lx+kx/ky*ly)/2;
t[4].a=t[4].b=0,t[4].c=lx*ny,t[4].p=t4;
t[1].f=t[2].f=t[3].f=t[4].f=1;
}
}
else
{
if(y1>=y3)
{
double t1=dx/kx+z2;
double t3=lx/kx+z2;
double t2=ly/ky+dx/kx+z2;
double t4=lx/kx+ly/ky+z2;
t[1].a=kx*ky/2,t[1].b=-dx*ky,t[1].c=ky*dx*dx/kx/2,t[1].p=t1;
if(t3<=t2)
{
t[2].a=0,t[2].b=ky*nx,t[2].c=-(ky*nx*(lx+dx))/(2*kx),t[2].p=t3;
t[3].p=t2;
}
else
{
t[2].a=0,t[2].b=kx*ly,t[2].c=-ly*ly*kx/ky/2-dx*ly,t[2].p=t2;
t[3].p=t3;
}
t[3].a=-kx*ky/2,t[3].b=ky*lx+kx*ly,t[3].c=nx*ly-(lx+kx/ky*ly)*(ly+ky/kx*lx)/2;
t[4].a=t[4].b=0,t[4].c=ly*nx,t[4].p=t4;
t[1].f=t[2].f=t[3].f=t[4].f=1;
}
else
{
double t1=dx/kx+dy/ky+z2;
double t2=lx/kx+dy/ky+z2;
double t3=dx/kx+ly/ky+z2;
double t4=lx/kx+ly/ky+z2;
t[1].a=kx*ky/2,t[1].b=-dx*ky-dy*kx,t[1].c=(dx+dy*kx/ky)*(dy+dx*ky/kx)/2,t[1].p=t1;
if(t2<=t3)
{
t[2].a=0,t[2].b=nx*ky,t[2].c=-nx*dy-nx*(dx+lx)*ky/(2*kx);
t[2].p=t2,t[3].p=t3;
}
else
{
t[2].a=0,t[2].b=ny*kx,t[2].c=-ny*dx-ny*(dy+ly)*kx/(2*ky);
t[2].p=t3,t[3].p=t2;
}
t[3].a=-kx*ky/2,t[3].b=(kx*ly+lx*ky),t[3].c=nx*ny-(lx+ly*kx/ky)*(ly+lx*ky/kx)/2;
t[4].a=t[4].b=0,t[4].c=ny*nx,t[4].p=t4;
t[1].f=t[2].f=t[3].f=t[4].f=1;
}
}
t[5].p=z3,t[5].f=2;
t[6].p=z4,t[6].f=-1;
t[7].p=z1,t[7].f=-1;
sort(t+1,t+8,cmp);
int f=0,g=0;
double na=0,nb=0,nc=0,pre,ans=0;
for(int i=1;i<=7;i++)
{
if(t[i].f==2)f=1;
else if(t[i].f==-1)
{
if(f&&!g)
{
// if(calc(na/3,nb/2,nc,t[i].p-z2)<calc(na/3,nb/2,nc,pre-z2))printf("%lld,%lld,%lld,%lld,%lld,%lld,%lld,%lld,%lld,%lld,%lld,%lld\n",x1,x2,x3,x4,y1,y2,y3,y4,z1,z2,z3,z4);
ans+=calc(na/3,nb/2,nc,t[i].p-z2)-calc(na/3,nb/2,nc,pre-z2);
}
g=1;
}
else
{
if(f&&!g)
{
// if(calc(na/3,nb/2,nc,t[i].p-z2)<calc(na/3,nb/2,nc,pre-z2))cout<<"i2="<<i<<'\n';
ans+=calc(na/3,nb/2,nc,t[i].p-z2)-calc(na/3,nb/2,nc,pre-z2);
}
na=t[i].a,nb=t[i].b,nc=t[i].c;
}
pre=t[i].p;
}
// if(ans<0)cout<<num<<'\n';
printf("%.8f\n",ans);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3760kb
input:
0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 2 2 2 0 0 0 1 1 1 0 2 0 2 0 2 1 0 1 0 1 0
output:
0.16666667 0.83333333 0.16666667
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 124ms
memory: 3764kb
input:
-3 -4 2 -5 -5 4 0 0 3 3 4 2 1 5 2 -4 0 0 5 -5 0 -2 -1 3 5 4 2 3 -5 -1 0 -2 -1 -4 -4 -3 -4 4 -2 -2 2 -1 2 2 1 4 0 5 -4 1 0 -5 -2 4 -5 2 -4 5 0 1 2 5 1 -1 0 -3 -1 5 -4 -4 2 -2 2 2 -4 1 3 -1 2 4 2 -2 1 3 2 5 2 -2 -3 -5 -1 0 0 5 4 2 2 5 3 -3 -3 -3 5 4 -4 1 2 -3 2 -4 2 -3 -2 -2 2 -2 -1 -4 -5 3 4 -3 -3 -3...
output:
0 0.00000000 0.00000000 0.00000000 0.70833333 0.00000000 0.00000000 15.35565476 0.00000000 6.56250000 0.00000000 0.00000000 0 0.00000000 0 0 0.00000000 0 0.00000000 0.00000000 0.00000000 1.31944444 0.00000000 0.52674897 4.65000000 0 0.00000000 0 1.92592593 0.00000000 0 0.00000000 0.00000000 0 15.868...
result:
ok 100000 numbers
Test #3:
score: 0
Accepted
time: 100ms
memory: 3648kb
input:
-2 -2 -9 1 7 6 -3 -1 -4 -5 -6 2 -3 -4 -9 -10 -5 -4 0 2 -6 7 -9 2 6 4 5 -2 -6 0 8 -8 -3 -3 -10 2 10 -3 -8 -7 -5 -10 -9 -5 1 10 8 -1 7 9 10 6 3 9 -10 -10 -4 0 2 1 -2 4 9 10 5 -4 -6 6 3 7 4 8 6 5 2 3 -7 8 2 3 1 4 -10 7 -7 -3 -6 -10 5 -9 0 3 1 -5 -6 8 5 -3 8 -8 -8 -4 5 -10 4 0 3 1 9 -9 0 -8 8 -3 -7 9 -2...
output:
0 0 0.00000000 0.00000000 0.00000000 16.25573225 0.16666667 0 26.20192308 1.44989107 0 0 0 0.00000000 1.28027682 0 0 0 13.43124041 0 0.00000000 0 0.04545455 0.00000000 18.29333333 0.00000000 58.04081633 0 0.00000000 1.73611111 0.00000000 0.00000000 0 0.00000000 144.00000000 43.90625000 0.00000000 0....
result:
ok 100000 numbers
Test #4:
score: 0
Accepted
time: 129ms
memory: 3764kb
input:
91 49 27 -66 89 -21 -22 35 78 -64 41 -19 93 87 -92 72 -32 -67 -48 28 -6 -50 20 78 -33 90 41 75 -51 43 89 9 -89 -35 -73 88 13 13 82 82 -40 72 -21 -75 36 15 79 -66 -21 -99 -49 -33 60 78 -27 -86 -64 61 66 96 -77 37 -71 72 -35 -9 38 86 -68 51 65 15 -16 -64 -25 -72 23 81 -20 60 60 -52 -99 19 24 83 27 -11...
output:
0 0.00000000 391.12720688 0.00000000 28313.21226415 0 11477.66256421 4368.00667701 14406.48359060 5814.42720107 0.00000000 50112.71688980 0.00000000 0 0.00000000 0 0 0 0 38.15140706 0.00000000 0 0.00000000 0 0.00000000 72.20194873 0 0.00000000 0.00000000 0.00000000 0.00000000 0 0.00000000 1923.68695...
result:
ok 100000 numbers
Test #5:
score: 0
Accepted
time: 134ms
memory: 3776kb
input:
-67 241 62 -271 -19 -199 364 487 343 293 433 -343 346 -321 78 -119 68 -487 -319 -45 -165 465 142 491 -310 476 -388 419 409 -124 167 -448 362 233 341 -119 9 -422 290 202 321 -217 310 216 286 172 10 -220 77 107 -282 352 -438 -26 171 81 111 -192 70 -132 376 -361 246 -371 354 -77 -400 -224 457 118 -387 ...
output:
0 417528.64696572 0.00000000 0.00000000 49064.27449541 5211742.51310033 3370766.24651518 0.00000000 0.00000000 84.40513354 165311.11770843 0.00000000 0.00000000 0 52736.15256096 0 132685.48097237 0 1436397.51531555 0.00000000 0.00000000 0.00000000 0.00000000 0.00000000 7356723.42700744 0 4878653.308...
result:
ok 100000 numbers