QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#22013#2839. 3D GeometryzmwangAC ✓134ms3776kbC++205.9kb2022-03-08 21:38:442022-04-30 00:41:01

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-30 00:41:01]
  • 评测
  • 测评结果:AC
  • 用时:134ms
  • 内存:3776kb
  • [2022-03-08 21:38:44]
  • 提交

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